CLOS生成实例确实很慢，并且会导致SBCL中的堆耗尽 [英] CLOS make-instance is really slow and causes heap exhaustion in SBCL
问题描述
我正在用Common Lisp(64位Debian GNU/Linux中的SBCL 1.1.5)编写一个多体系结构的汇编器/反汇编器，当前该汇编器为x86-64的子集生成正确的代码.为了汇编x86-64汇编代码，我使用一个哈希表，其中诸如"jc-rel8"和"stosb"之类的汇编指令助记符(字符串)是返回1个或多个编码函数列表的键，如下所示:
I'm writing an multiarchitecture assembler/disassembler in Common Lisp (SBCL 1.1.5 in 64-bit Debian GNU/Linux), currently the assembler produces correct code for a subset of x86-64. For assembling x86-64 assembly code I use a hash table in which assembly instruction mnemonics (strings) such as "jc-rel8" and "stosb" are keys that return a list of 1 or more encoding functions, like the ones below:
(defparameter *emit-function-hash-table-x64* (make-hash-table :test 'equalp))
(setf (gethash "jc-rel8" *emit-function-hash-table-x64*) (list #'jc-rel8-x86))
(setf (gethash "stosb" *emit-function-hash-table-x64*) (list #'stosb-x86))
编码功能如下(虽然有些更复杂):
The encoding functions are like these (some are more complicated, though):
(defun jc-rel8-x86 (arg1 &rest args)
(jcc-x64 #x72 arg1))
(defun stosb-x86 (&rest args)
(list #xaa))
现在，我正在尝试通过使用 NASM(NASM 2.11.06)指令编码数据(文件 insns.dat )转换为Common Lisp CLOS句法.这意味着用自定义x86-asm-instruction类(到目前为止是一个非常基本的类，用:initarg，:reader，:initform等大约20个插槽)的实例替换用于发出二进制代码的常规函数(如上述函数) .)，其中带有自变量的emit方法将用于发出给定指令(助记符)和自变量的二进制代码.转换后的指令数据看起来像这样(但超过40'000行，分别是7193 make-instance和7193 setf).
Now I am trying to incorporate the complete x86-64 instruction set by using NASM's (NASM 2.11.06) instruction encoding data (file insns.dat) converted to Common Lisp CLOS syntax. This would mean replacing regular functions used for emitting binary code (like the functions above) with instances of a custom x86-asm-instruction class (a very basic class so far, some 20 slots with :initarg, :reader, :initform etc.), in which an emit method with arguments would be used for emitting the binary code for given instruction (mnemonic) and arguments. The converted instruction data looks like this (but it's more than 40'000 lines and exactly 7193 make-instance's and 7193 setf's).
;; first mnemonic + operand combination instances (:is-variant t).
;; there are 4928 such instances for x86-64 generated from NASM's insns.dat.
(eval-when (:compile-toplevel :load-toplevel :execute)
(setf Jcc-imm-near (make-instance 'x86-asm-instruction
:name "Jcc"
:operands "imm|near"
:code-string "[i: odf 0f 80+c rel]"
:arch-flags (list "386" "BND")
:is-variant t))
(setf STOSB-void (make-instance 'x86-asm-instruction
:name "STOSB"
:operands "void"
:code-string "[ aa]"
:arch-flags (list "8086")
:is-variant t))
;; then, container instances which contain (or could be refer to instead)
;; the possible variants of each instruction.
;; there are 2265 such instances for x86-64 generated from NASM's insns.dat.
(setf Jcc (make-instance 'x86-asm-instruction
:name "Jcc"
:is-container t
:variants (list Jcc-imm-near
Jcc-imm64-near
Jcc-imm-short
Jcc-imm
Jcc-imm
Jcc-imm
Jcc-imm)))
(setf STOSB (make-instance 'x86-asm-instruction
:name "STOSB"
:is-container t
:variants (list STOSB-void)))
;; thousands of objects more here...
) ; this bracket closes (eval-when (:compile-toplevel :load-toplevel :execute)
我已经使用一个琐碎的Perl脚本(在下面进一步介绍，但脚本本身没有兴趣)将NASM的insns.dat转换为Common Lisp语法(如上).这样就可以了，但是编译这7193个对象确实非常慢，并且通常会导致堆耗尽.在我的具有16G内存的Linux Core i7-2760QM笔记本电脑上，编译具有上述7193个对象的(eval-when (:compile-toplevel :load-toplevel :execute)代码块需要7分钟以上的时间，有时会导致堆耗尽，如下所示:
I have converted NASM's insns.dat to Common Lisp syntax (like above) using a trivial Perl script (further below, but there's nothing of interest in the script itself) and in principle it works. So it works, but compiling those 7193 objects is really really slow and commonly causes heap exhaustion. On my Linux Core i7-2760QM laptop with 16G of memory the compiling of an (eval-when (:compile-toplevel :load-toplevel :execute) code block with 7193 objects like the ones above takes more than 7 minutes and sometimes causes heap exhaustion, like this one:
;; Swank started at port: 4005.
* Heap exhausted during garbage collection: 0 bytes available, 32 requested.
Gen StaPg UbSta LaSta LUbSt Boxed Unboxed LB LUB !move Alloc Waste Trig WP GCs Mem-age
0: 0 0 0 0 0 0 0 0 0 0 0 41943040 0 0 0.0000
1: 0 0 0 0 0 0 0 0 0 0 0 41943040 0 0 0.0000
2: 0 0 0 0 0 0 0 0 0 0 0 41943040 0 0 0.0000
3: 38805 38652 0 0 49474 15433 389 416 0 2144219760 9031056 1442579856 0 1 1.5255
4: 127998 127996 0 0 45870 14828 106 143 199 1971682720 25428576 2000000 0 0 0.0000
5: 0 0 0 0 0 0 0 0 0 0 0 2000000 0 0 0.0000
6: 0 0 0 0 1178 163 0 0 0 43941888 0 2000000 985 0 0.0000
Total bytes allocated = 4159844368
Dynamic-space-size bytes = 4194304000
GC control variables:
*GC-INHIBIT* = true
*GC-PENDING* = in progress
*STOP-FOR-GC-PENDING* = false
fatal error encountered in SBCL pid 9994(tid 46912556431104):
Heap exhausted, game over.
Welcome to LDB, a low-level debugger for the Lisp runtime environment.
ldb>
我必须为SBCL添加--dynamic-space-size 4000参数以完全对其进行编译，但是仍然在分配4 GB的动态空间堆后有时会用尽.即使可以解决堆耗尽的问题，在类(对于这些实例使用的'x86-asm-instruction类)中添加一个插槽之后，超过7分钟的时间编译7193个实例对于REPL中的交互式开发来说也太多了(我使用 ="http://www.vim.org/scripts/script.php?script_id=2531"> slimv .
I had to add --dynamic-space-size 4000 parameter for SBCL to get it compiled at all, but still after allocating 4 gigabytes of dynamic space heap sometimes gets exhausted. Even if the heap exhaustion would be solved, more than 7 minutes for compiling 7193 instances after only adding a slot in the class ('x86-asm-instruction class used for these instances) is way too much for interactive development in REPL (I use slimv, if that matters).
以下是(time (compile-file输出:
; caught 18636 WARNING conditions
; insns.fasl written
; compilation finished in 0:07:11.329
Evaluation took:
431.329 seconds of real time
238.317000 seconds of total run time (234.972000 user, 3.345000 system)
[ Run times consist of 6.073 seconds GC time, and 232.244 seconds non-GC time. ]
55.25% CPU
50,367 forms interpreted
784,044 lambdas converted
1,031,842,900,608 processor cycles
19,402,921,376 bytes consed
使用OOP(CLOS)将能够合并指令助记符(例如上面的jc或stosb，:name)，指令的允许操作数(:operands)，指令的二进制编码(例如stosb，:code-string)和一个对象中指令的可能体系结构限制(:arch-flags).但是，看来至少我使用了3年的计算机的效率不足以快速编译大约7000个CLOS对象实例.
Using OOP (CLOS) would enable incorporating the instruction mnemonic (such as jc or stosb above, :name), allowed operands of the instruction (:operands), instruction's binary encoding (such as #xaa for stosb, :code-string) and possible architecture limitations (:arch-flags) of the instruction in one object. But it seems that at least my 3-year-old computer is not efficient enough to compile around 7000 CLOS object instances quickly.
我的问题是:有什么方法可以使SBCL的make-instance更快，还是应该在常规函数(如上面的示例)中保持汇编代码的生成?我也很高兴知道任何其他可能的解决方案.
My question is: Is there some way to make SBCL's make-instance faster, or should I keep assembly code generation in regular functions like the examples further above? I'd be also very happy to know about any other possible solutions.
这里是Perl脚本，以防万一:
Here's the Perl script, just in case:
#!/usr/bin/env perl
use strict;
use warnings;
# this program converts NASM's `insns.dat` to Common Lisp Object System (CLOS) syntax.
my $firstchar;
my $line_length;
my $are_there_square_brackets;
my $mnemonic_and_operands;
my $mnemonic;
my $operands;
my $code_string;
my $flags;
my $mnemonic_of_current_mnemonic_array;
my $clos_object_name;
my $clos_mnemonic;
my $clos_operands;
my $clos_code_string;
my $clos_flags;
my @object_name_array = ();
my @mnemonic_array = ();
my @operands_array = ();
my @code_string_array = ();
my @flags_array = ();
my @each_mnemonic_only_once_array = ();
my @instruction_variants_array = ();
my @instruction_variants_for_current_instruction_array = ();
open(FILE, 'insns.dat');
$mnemonic_of_current_mnemonic_array = "";
# read one line at once.
while (<FILE>)
{
$firstchar = substr($_, 0, 1);
$line_length = length($_);
$are_there_square_brackets = ($_ =~ /\[.*\]/);
chomp;
if (($line_length > 1) && ($firstchar =~ /[^\t ;]/))
{
if ($are_there_square_brackets)
{
($mnemonic_and_operands, $code_string, $flags) = split /[\[\]]+/, $_;
$code_string = "[" . $code_string . "]";
($mnemonic, $operands) = split /[\t ]+/, $mnemonic_and_operands;
}
else
{
($mnemonic, $operands, $code_string, $flags) = split /[\t ]+/, $_;
}
$mnemonic =~ s/[\t ]+/ /g;
$operands =~ s/[\t ]+/ /g;
$code_string =~ s/[\t ]+/ /g;
$flags =~ s/[\t ]+//g;
# we don't want non-x86-64 instructions here.
unless ($flags =~ "NOLONG")
{
# ok, the content of each field is now filtered,
# let's convert them to a suitable Common Lisp format.
$clos_object_name = $mnemonic . "-" . $operands;
# in Common Lisp object names `|`, `,`, and `:` must be escaped with a backslash `\`,
# but that would get too complicated.
# so we'll simply replace them:
# `|` -> `-`.
# `,` -> `.`.
# `:` -> `.`.
$clos_object_name =~ s/\|/-/g;
$clos_object_name =~ s/,/./g;
$clos_object_name =~ s/:/./g;
$clos_mnemonic = "\"" . $mnemonic . "\"";
$clos_operands = "\"" . $operands . "\"";
$clos_code_string = "\"" . $code_string . "\"";
$clos_flags = "\"" . $flags . "\""; # add first and last double quotes.
$clos_flags =~ s/,/" "/g; # make each flag its own Common Lisp string.
$clos_flags = "(list " . $clos_flags. ")"; # convert to `list` syntax.
push @object_name_array, $clos_object_name;
push @mnemonic_array, $clos_mnemonic;
push @operands_array, $clos_operands;
push @code_string_array, $clos_code_string;
push @flags_array, $clos_flags;
if ($mnemonic eq $mnemonic_of_current_mnemonic_array)
{
# ok, same mnemonic as the previous one,
# so the current object name goes to the list.
push @instruction_variants_for_current_instruction_array, $clos_object_name;
}
else
{
# ok, this is a new mnemonic.
# so we'll mark this as current mnemonic.
$mnemonic_of_current_mnemonic_array = $mnemonic;
push @each_mnemonic_only_once_array, $mnemonic;
# we first push the old array (unless it's empty), then clear it,
# and then push the current object name to the cleared array.
if (@instruction_variants_for_current_instruction_array)
{
# push the variants array, unless it's empty.
push @instruction_variants_array, [ @instruction_variants_for_current_instruction_array ];
}
@instruction_variants_for_current_instruction_array = ();
push @instruction_variants_for_current_instruction_array, $clos_object_name;
}
}
}
}
# the last instruction's instruction variants must be pushed too.
if (@instruction_variants_for_current_instruction_array)
{
# push the variants array, unless it's empty.
push @instruction_variants_array, [ @instruction_variants_for_current_instruction_array ];
}
close(FILE);
# these objects need be created already during compilation.
printf("(eval-when (:compile-toplevel :load-toplevel :execute)\n");
# print the code to create each instruction + operands combination object.
for (my $i=0; $i <= $#mnemonic_array; $i++)
{
$clos_object_name = $object_name_array[$i];
$mnemonic = $mnemonic_array[$i];
$operands = $operands_array[$i];
$code_string = $code_string_array[$i];
$flags = $flags_array[$i];
# print the code to create a variant object.
# each object here is a variant of a single instruction (or a single mnemonic).
# actually printed as 6 lines to make it easier to read (for us humans, I mean), with an empty line in the end.
printf("(setf %s (make-instance 'x86-asm-instruction\n:name %s\n:operands %s\n:code-string %s\n:arch-flags %s\n:is-variant t))",
$clos_object_name,
$mnemonic,
$operands,
$code_string,
$flags);
printf("\n\n");
}
# print the code to create each instruction + operands combination object.
# for (my $i=0; $i <= $#each_mnemonic_only_once_array; $i++)
for my $i (0 .. $#instruction_variants_array)
{
$mnemonic = $each_mnemonic_only_once_array[$i];
# print the code to create a container object.
printf("(setf %s (make-instance 'x86-asm-instruction :name \"%s\" :is-container t :variants (list \n", $mnemonic, $mnemonic);
@instruction_variants_for_current_instruction_array = $instruction_variants_array[$i];
# for (my $j=0; $j <= $#instruction_variants_for_current_instruction_array; $j++)
for my $j (0 .. $#{$instruction_variants_array[$i]} )
{
printf("%s", $instruction_variants_array[$i][$j]);
# print 3 closing brackets if this is the last variant.
if ($j == $#{$instruction_variants_array[$i]})
{
printf(")))");
}
else
{
printf(" ");
}
}
# if this is not the last instruction, print two newlines.
if ($i < $#instruction_variants_array)
{
printf("\n\n");
}
}
# print the closing bracket to close `eval-when`.
print(")");
exit;
推荐答案
18636警告看起来真的很糟糕，首先要消除所有警告.
我将从摆脱所有这些方面的EVAL-WHEN开始.对我来说没有多大意义.直接加载文件，或编译并加载文件.
I would start by getting rid of the EVAL-WHEN around all that. Does not make much sense to me. Either load the file directly, or compile and load the file.
还请注意，当变量未定义时，SBCL不喜欢(setf STOSB-void ...). DEFVAR或DEFPARAMETER引入了新的顶级变量. SETF只是设置它们，但没有定义它们.这应该有助于摆脱警告.
Also note that SBCL does not like (setf STOSB-void ...) when the variable is undefined. New top-level variables are introduced with DEFVAR or DEFPARAMETER. SETF just sets them, but does not define them. That should help to get rid of the warnings.
还有:is-container t和:is-variant t的气味，这些属性应转换为要继承的类(例如，作为mixin).容器具有变体.变体没有变体.
Also :is-container t and :is-variant t smell like these properties should be converted into classes to inherit from (for example as a mixin). A container has variants. A variant does not have variants.
这篇关于CLOS生成实例确实很慢，并且会导致SBCL中的堆耗尽的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
