Hi Tomas,

now I changed 'sort' as discussed, accepting an optional function
argument.

It is available in the testing release.

As described, some data have to be preserved in stack frames, to be
gc-safe. The code is quite a mess with that now, but the changes were
straightforward. The performance of the default invocation does not seem
to change, so the overhead is really negligible.

   : (let L (make (do 100000 (link (rand)))) (bench (sort L))) T

is around 0.18 seconds on my notebook, both in the old and in the new
version.


Also, the equivalent call, passing the function '<'

   : (let L (make (do 100000 (link (rand)))) (bench (sort L) <)) T

does not change much (around 0.2 seconds).


More interesting (and as I expected) is the difference between sorting
by unary or binary criteria:

The "unary" call

   : (let L (make (do 100000 (link (rand)))) (bench (by - sort L))) T

takes about 0.35 seconds, while the "binary" call

   : (let L (make (do 100000 (link (rand)))) (bench (sort L '((A B) (< (- A) (- 
B)))))) T

needs 1.8 seconds on the avarage.

This is because in the binary version the "retrieval" function (here the
negation with '-') needs to be applied much more often (about
O(2*N*log(N)) times) to the data than in the unary one (exact O(N)).

Cheers,
- Alex
-- 
UNSUBSCRIBE: mailto:picol...@software-lab.de?subject=unsubscribe

Reply via email to