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 <[EMAIL PROTECTED]> writes: > You might consider sort, remove, and nconc. > > Thanks, > > Bob > > -- Camm Maguire [EMAIL PROTECTED] ========================================================================== "The earth is but one country, and mankind its citizens." -- Baha'u'llah _______________________________________________ Gcl-devel mailing list [email protected] http://lists.gnu.org/mailman/listinfo/gcl-devel
