Som v 1.7
New virtual machine and update som v1.5 to add features of som-v2 as
follows:
New features
1) new Virtual machine, T-code,
3 times
faster than som v1.5
2) use hash in symbol table, (symtab5-s.txt in som-v2)
3) use snapshot with new object layout
(include DS)
4) dynamic load source file
(syscall 11)
and add some new syntax
5) static array:
a = array {1 2
3}
6) hex number:
#ff
this is already done in som v1 but not enable (see
som1/parser/parse.txt and lex.c).
7) add named file i/o to handle more than one stream. (see
example code in \test\file-s.txt)
presently som-v15 has print,
printc, getchar
som-v17 add fopen, fclose,
fprint, fprintc, fgetc
syscall number:
1
print
2 printc
3 getchar
4 -
5 fopen
6 fclose
7 fprint
8 fprintc
9 fgetc
10 array
11 load
T-code specification
Som v1.7 is based on a new virtual machine. The new instruction
set, called T-code, is register-based. The instruction is
3-address format. T-code is a register-based VM as opposed to
S-code which is stack-based (in the same sense as JVM). As T-code
is 3-address format, it has less number of instruction executed
(dynamic instruction count) than S-code. The data from various
chip designs pointed to 40% number of instruction executed of S-code
[aisd eecon 2003, sr, compact code jcsse 2005, xs]. This means if
all else is equal, T-code vm will be 2.5 times faster than
s-code. The implementation of T-code is carefully engineered and
the result (measured running all solutions of 8-queen problem) shows it
is 3 times faster than som v1.5.
So, Som v1.7 is going for speed. However, it will not be complex.
For example, the number of instruction is not much larger than s-code,
T-code is 54 instructions vs. S-code 44 instructions. The compiler
optimisation should not be too complex either (to make future change
simple).
The next release I would like to upgrade Som-v2 to Som-v2.3 to be
analogous to v1.7 (but is all in Som).
23 December 2005
Dynamic load
Finally, in this release (v1.7) the dynamic load is available (after 2
attempts in the past years which ended in failure). Dynamic load
requires the ability to do recursive load. The most intrigue part
is how to handle internal states of "lex" (the lexical analyser).
Lex uses many states to do indentation as blocks (see the source
lex.c). After many designs, the best solution comes from treating
a file as a unit of compilation. It means one whole file will be
compiled (generated executable codes) until completion before executing
any immediate lines (which have already been compiled into executable
codes). During the execution of the immediate lines, loading of
another source file may occurs. It can happen recursively.
With this design, "lex" is reset to a known initial state for each file
because one file will be completed before the next. It is not
necessary to save/restore any states, or any buffer. Hence, the
problem is solved!
eval() may be called recursively. The global state of the
interpreter is fp. fp is used in the manner of LIFO hence needed
not to be saved. ip is local to eval, so eval() is
reentrant. When doing eval() and encounters "load" (syscall 11),
this causes the interpreter to start compiling a new file and executing
the immediate lines in that file by calling eval() recursively.
A source file is compiled as a unit, therefore any forward reference to
a function must be declared properly. Remember that this file
will be compiled to the completion before starting a next one.
See the following example:
<file
t1.txt>
aa = 11
to t1 x = x + 1
to t2 x = {} //
forward declare of func "t2"
load "t2.txt"
print t1 2 print t2 3
<end>
<file t2.txt>
bb = 22
to t2 x = x + 2
<end>
The file "t1.txt" loads "t2.txt". However, "print t2 3" in t1.txt
refers to the function "t2" in other source file not yet
compiled. Therefore the function "t2" must be declare forwardly
in the file "t1.txt" before it can be used. (the compiler must
know its arity to compile "print t2 3" properly). To declare a
function forwardly, only the function head must be presented, the body
is empty.
Dynamic load enables writing a program as "modules". A module
contains related functions. Each module is in a separate source
file. A "master" file can be written to contain mainly loading
other modules. The dynamic load helps to manage source files and
allows their reuse.
Benchmark
som v1.7 is benchmark against som v1.5. Table 1 shows the
number of instruction executed. T-machine has less than half the
number of instruction executed than S-mcahine. On average
T-machine execute 40% noi. of S-machine.
Table 1 Comparing the number of instruction executed between
T-machine and S-machine
program
|
noi T-code
|
noi S-code
|
| bubble (20 items) |
4207
|
11925
|
| hanoi (6 disks) |
1238
|
2317
|
| matmul2 (4x4 mul3) |
4116
|
13886
|
| perm (4 digits) |
1839
|
5469
|
| queen2 (all soln) |
221578
|
443344
|
| quick (20 items) |
1748
|
3972
|
| sieve (<= 500) |
5250
|
17151
|
| aes4 |
11127
|
28609*
|
* data from vy2, aes4 (aes2 with static array) by vy2 noi is 28609, vy2
is slightly better than s-machine
In term of running time, som v1.7 and som v1.5 run "queen2.obj"
in excecute only mode 10 times to measure only the effectiveness of
interpreter. The measurement is repeated 3 times. som v1.7
is 3.4 times faster than som v1.5 (mostly because of engineering
of the interpreter, T-code itself contributes around 25% speedup
compared with S-code when all things are equal).
Table 2 Comparing the running time of som v1.7 and som v1.5
execution time (run queen2.obj 10 times)
som-v15 4.091, 3.558, 3.914
som-v17 0.248, 0.244, 0.243
11 Jan 2006
<note correction to the speedup figures, 5 Aug 2008. The
figure above is incorrect>
running queen2.obj 100 times, v18 has the same vm as v17. These
figures are from birthday/doc/all-som.performance.xls, Aug 2008.
som-v15 1792 ms
som-v18 531 ms
speedup is (1- v18/v15) * 100 = 70.4% or
3.4x
last update 21 Feb 2024