clisp-devel

1 extra bytecode instruction per variable per loop

[Sam S. <sd...@gn...>]

Hi Bruno,

The fix for https://sourceforge.net/p/clisp/bugs/375/
(https://sourceforge.net/p/clisp/clisp/ci/52d209b7d29ddf1125d2d89f4185c20c2f09da12/)
introduces an extra binding per init expression.
This results in an extra bytecode instruction in the preamble, e.g.,
for (loop repeat 100 for a on b for x in y collect (list a x)):

--8<---------------cut here---------------start------------->8---
Disassembly of function :LAMBDA
(CONST 0) = 100
(CONST 1) = B
(CONST 2) = Y
0 required arguments
0 optional arguments
No rest parameter
No keyword parameters
reads special variables: Y B
27 byte-code instructions:
0     (CONST&PUSH 0)                      ; 100
1     (PUSH-NIL 4)
3     (GETVALUE 1)                        ; B
5     (STORE 3)
6     (GETVALUE 2)                        ; Y
8     (STORE 2)
9     (JMP L26)
11    L11
--8<---------------cut here---------------end--------------->8---

becomes

--8<---------------cut here---------------start------------->8---
Disassembly of function :LAMBDA
(CONST 0) = B
(CONST 1) = Y
(CONST 2) = 100
0 required arguments
0 optional arguments
No rest parameter
No keyword parameters
reads special variables: Y B
29 byte-code instructions:
0     (GETVALUE&PUSH 0)                   ; B
2     (GETVALUE&PUSH 1)                   ; Y
4     (CONST&PUSH 2)                      ; 100
5     (PUSH-NIL 4)
7     (LOAD 6)
8     (STORE 3)
9     (LOAD 5)
10    (STORE 2)
11    (JMP L28)
13    L13
--8<---------------cut here---------------end--------------->8---

The cost is probably trivial, but I wonder if there is some simple
compilation optimization missing here...

Thanks

-- 
Sam Steingold (http://sds.podval.org/) on darwin Ns 10.3.1504
http://steingoldpsychology.com http://www.childpsy.net http://www.memritv.org
http://iris.org.il http://americancensorship.org https://jihadwatch.org
"Sustainability" without "population growth control" is hypocrisy.

Re: 1 extra bytecode instruction per variable per loop

[<Joe...@t-...>]

Hi,

Sam Steingold wrote:
>The fix for https://sourceforge.net/p/clisp/bugs/375/
>(https://sourceforge.net/p/clisp/clisp/ci/52d209b7d29ddf1125d2d89f4185c20c2f09da12/)
>introduces an extra binding per init expression.
>This results in an extra bytecode instruction in the preamble, e.g., for
>(loop repeat 100 for a on b for x in y collect (list a x)):

Next to a cost in bytecode, there's also a memory footprint. Given
that clisp's compiler doesn't perform liveness analysis,
  (LET ((s b)) (LOOP/PROG/TAGBODY #))
means that the binding for s will remain on the stack (where the value
of s is held) for the whole duration of the loop. CLISP doesn't
notice that s is only used once, in the loop initialization code and
never afterwards.

This reminds me of the discussion of GC leaks in functional programming.

Hence it would be best if
  (loop repeat 100 for a on b for x in y collect (list a x))
could expand to
  (let* ((a b) (list-x y)(x #)) (prog ...))
without much intermediates.

Regards,
	Jörg

Re: 1 extra bytecode instruction per variable per loop

[Bruno H. <br...@cl...>]

Hi Sam,

> --8<---------------cut here---------------start------------->8---
> Disassembly of function :LAMBDA
> (CONST 0) = 100
> (CONST 1) = B
> (CONST 2) = Y
> 0 required arguments
> 0 optional arguments
> No rest parameter
> No keyword parameters
> reads special variables: Y B
> 27 byte-code instructions:
> 0     (CONST&PUSH 0)                      ; 100
> 1     (PUSH-NIL 4)
> 3     (GETVALUE 1)                        ; B
> 5     (STORE 3)
> 6     (GETVALUE 2)                        ; Y
> 8     (STORE 2)
> 9     (JMP L26)
> 11    L11
> --8<---------------cut here---------------end--------------->8---
> 
> becomes
> 
> --8<---------------cut here---------------start------------->8---
> Disassembly of function :LAMBDA
> (CONST 0) = B
> (CONST 1) = Y
> (CONST 2) = 100
> 0 required arguments
> 0 optional arguments
> No rest parameter
> No keyword parameters
> reads special variables: Y B
> 29 byte-code instructions:
> 0     (GETVALUE&PUSH 0)                   ; B
> 2     (GETVALUE&PUSH 1)                   ; Y
> 4     (CONST&PUSH 2)                      ; 100
> 5     (PUSH-NIL 4)
> 7     (LOAD 6)
> 8     (STORE 3)
> 9     (LOAD 5)
> 10    (STORE 2)
> 11    (JMP L28)
> 13    L13
> --8<---------------cut here---------------end--------------->8---
> 
> The cost is probably trivial, but I wonder if there is some simple
> compilation optimization missing here...

The missing compiler optimization is a full data flow analysis.

clisp's compiler supports data flow analysis for simple cases (e.g.
a variable that is only bound to an initform and never assigned).
More complex cases that would require multiple passes are not
implemented.

The LOOP macro (and other macros) have been written in a way to
generate good bytecode.

Bruno