This is a system to access very large lists by index.
First of all, let me say, that the idea for this started
in another thread some days ago. There, I proposed another
idea, with the same goal.
I have to say that overall, Alex, you were right. I insisted
too much, defending that system.
It is my opinion, that the biggest objection, was the need
to make use of C heap space outside of the regular picolisp
cell pool.
Now, here is exposed, another system for the same goal.
HELPER LIST
-----------
We need a helper function to build an index list from the
large original list:
(de leap (L)
(make (for (P L P (nth P 9)) (link P))) )
(de helper (L)
(leap(leap(leap(leap(leap(leap L)))))) )
We initialize the original list, and build the helper list:
(setq A (need 2000000 0) # two million elements list
B (helper A) )
At my computer, the helper function takes 0.050 seconds to
index this 2 million elements list. It would take 0.003 seconds
to index an 50000 elements list, for reference.
fastNth PRIMITIVE
-----------------
We now define a new primitive function, in order to traverse
the helper list. (I have added it to the /src/subr.c file of
the picolisp source code).
any doFastNth(any ex) {
any x = cdr(ex);
int n = (unDig(EVAL(cadr(x)))>>1) - 1;
x = EVAL(car(x));
NeedVar(ex,x);
int i;
int A = 7 & n;
int B = 7 & (n >>= 3);
int C = 7 & (n >>= 3);
int D = 7 & (n >>= 3);
int E = 7 & (n >>= 3);
int F = 7 & (n >>= 3);
int G = (n >> 3);
for (i = 0; i < G; ++i) x = cdr(x); x = car(x);
for (i = 0; i < F; ++i) x = cdr(x); x = car(x);
for (i = 0; i < E; ++i) x = cdr(x); x = car(x);
for (i = 0; i < D; ++i) x = cdr(x); x = car(x);
for (i = 0; i < C; ++i) x = cdr(x); x = car(x);
for (i = 0; i < B; ++i) x = cdr(x); x = car(x);
for (i = 0; i < A; ++i) x = cdr(x);
return x;
}
(*) I had to add as well this line to /src/pico.h:
any doFastNth(any);
(*) And this line to /src/tab.c:
{doFastNth, "fastNth"},
PICOLISP EQUIVALENT FUNCTION
------------------------------------------------
(de fastNth (L N)
(dec 'N) # convert 1-offset convention to 0-offset
(let (A (& 7 N)
B (& 7 (setq N (>> 3 N)))
C (& 7 (setq N (>> 3 N)))
D (& 7 (setq N (>> 3 N)))
E (& 7 (setq N (>> 3 N)))
F (& 7 (setq N (>> 3 N)))
G (>> 3 N) )
(nth L (inc G) (inc F) (inc E) (inc D) (inc C) (inc B) (inc A)) ) )
TIMING FUNCTIONS:
-----------------
We now define the timing functions:
(de access (N) # a million times nth execution to the N nth-element
(do 100000
(nth A N) (nth A N) (nth A N) (nth A N) (nth A N)
(nth A N) (nth A N) (nth A N) (nth A N) (nth A N) )
T )
(de access-fast (N) # a million times fastNth execution to the N nth-element
(do 100000
(fastNth B N) (fastNth B N) (fastNth B N) (fastNth B N) (fastNth B N)
(fastNth B N) (fastNth B N) (fastNth B N) (fastNth B N) (fastNth B N) )
T )
Results:
(access 1) = 0.081 seconds <- Time Reference!
(access-fast 1) = 0.081 seconds, same time
(access-fast 10) = 0.085 seconds, 1.05 times slower
(access-fast 100) = 0.095 seconds, 1.17 times slower
(access-fast 1000) = 0.115 seconds, 1.42 times slower
(access-fast 10000) = 0.118 seconds, 1.47 times slower
(access-fast 100000) = 0.124 seconds, 1.53 times slower
(access-fast 1000000) = 0.139 seconds, 1.71 times slower
(access-fast 2000000) = 0.139 seconds, 1.71 times slower
RESULTS
-------
On average, the fastNth accessor, coded in C, is only 1.5 times slower
than a pure array C implementation. The helper list is always 1/7th
the size of the original large list.
This system makes the access to very large lists by index a reality,
the only thing required is a new fastNth primitive function.
It is my opinion, that a little primitive like this, is worthwhile to
have in the picolisp toolbox.
The Picolisp equivalent function showed, is on average 45 times slower
than a pure array C implementation.
Best Regards
Enrique.
--
UNSUBSCRIBE: mailto:[email protected]?subject=Unsubscribe