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

Reply via email to