[Gcl-devel] Re: sequences / in-lining

[Camm Maguire]

Greetings!  

Here is something:

=============================================================================
2.6.7
==================================================================
(setq q (let (r) (dotimes (i 1000000) (push (random 1000000) r)) r) b nil)

NIL

>(defun foo (x) (sort x '>))

FOO

>(compile 'foo)

Compiling gazonk0.lsp.
End of Pass 1.  
End of Pass 2.  
OPTIMIZE levels: Safety=0 (No runtime error checking), Space=0, Speed=3
Finished compiling gazonk0.lsp.
Loading gazonk0.o
start address -T 0x83ee940 Finished loading gazonk0.o
#<compiled-function FOO>
NIL
NIL

>(setq l1 (copy-list q) l2 (copy-list q) b nil)

NIL

>(time (progn (setq l2 (foo l2)) nil))

real time       :      5.670 secs
run-gbc time    :      5.640 secs
child run time  :      0.000 secs
gbc time        :      0.000 secs
NIL

>(time (progn (setq l2 (foo l2)) nil))

real time       :      6.060 secs
run-gbc time    :      5.620 secs
child run time  :      0.000 secs
gbc time        :      0.430 secs
NIL

>
==================================================================
cvs head with latest commits today
=============================================================================
(time (progn (setq l2 (foo l2)) nil))

real time       :      0.960 secs
run-gbc time    :      0.950 secs
child run time  :      0.000 secs
gbc time        :      0.000 secs
NIL

>(time (progn (setq l2 (foo l2)) nil))

real time       :      0.560 secs
run-gbc time    :      0.550 secs
child run time  :      0.000 secs
gbc time        :      0.000 secs
NIL

>
=============================================================================

These appear to compare favorably to other implementations. The key is
that the predicate (and key if supplied) are inlined.  Four forms are
accepted ((lambda () ...) #'(lambda () ...) 'f #'f). Lists are
actually sorted faster than vectors by default as if one does not know
the underlying type, one has to call aref and aset, etc.  Declaring
the vector type at the top makes the sort faster than with lists.
quick-sort is used for both, with a backing array created for lists.
branch elimination is done based on any outer scope type information
available, otherwise the inlining is done twice.  I think in most
cases we will be able to discern vector from list at compile time,
though this needs (just a little, I think) more work.

Also inlined are: length and reverse, endp and identity are expanded,
the former to throw an error only when safety >=1.

There is an unused heap sort in the code too, but I can't see any gain
here, as the memory requirements are virtually the same.  The
quick-sort is non-recursive and uses a tiny stack ~ log_2(n).  I have
to read up on what stable-sort is supposed to be.

More to follow.  Feedback appreciated.  Notably, sort is likely the
biggest inline we would ever consider, and its impact on code size
might be arguable.  But it certainly pays off in performance.

Take care,

Robert Boyer <address@hidden> writes:

> You might consider sort, remove, and nconc.
> 
> Thanks,
> 
> Bob
> 
> 

-- 
Camm Maguire                                            address@hidden
==========================================================================
"The earth is but one country, and mankind its citizens."  --  Baha'u'llah