1) A pragmatic solution
2) Some timing results and a workaround
1) A PRAGMATIC SOLUTION
-----------------------
Is there a price to be paid for having arrays in the language?
Well, if the picolisp machine has to be changed, in order to support
another data type, more tag bits, then I would say that is a big price
to be paid.
But an array doesn't necessarily need to be another data type.
An array can be used in the same way as file handles are used in
operating systems, with no need to change the picolisp machine.
Examples of array definition:
(setq *Ram (array 65536))
(setq *Rom (array 65536))
(setq *Per (array (permute (range 1 65536))))
afterwards -> *Ram= 1, *Rom= 2, *Per= 3
The function 'array takes one parameter
a number,
or an already built list.
In general, things like (setq A (array N)) would trigger something
like this in C:
int current;
arrays[++current] = malloc(N * (sizeof CELL*));
return makeNUMBER(current);
Arrays would be internally arrays of pointers to CELLS,
and externally just an integer handle.
So we could use arrays thru 4 functions:
(setq *Ram (array 65536))
(get: *Ram 50000)
(set: *Ram 50000 (33 52 8 91))
(dispose *Ram)
NOTES:
1) The function 'array could possibly return the memory pointer of the
newly allocated array instead of the integer handle, for speed.
2) I suppose that the garbage collector would have to keep track of
all those CELL pointers in the array, that are outside of the reach of
the picolisp symbol table. That would be the price to pay, I think
a smaller price than adding another datatype.
3) The array, as defined here, would not be addressable as a
whole, as a structure, because it's physically outside of the main
cell heap. But the elements could be manipulated individually thru
'get: and 'set: , and that is the main purpose of arrays.
2) SOME TIMING RESULTS AND A WORKAROUND
---------------------------------------
(setq A (need 65536)) # big array as list
(de normalAccess (N) # 50000 accesses to the N nth-element
(do 5000
(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) ) )
(bench (normalAccess 1)) gives 0.007 seconds
(bench (normalAccess 100)) gives 0.020 seconds (2.85 times slower)
(bench (normalAccess 50000)) gives 9.100 seconds (1300 times slower)
This is a workaround using a helper list to traverse a big list:
# Diagram of a 64k list and its helper index list:
# A = (0 ... 256 ... 512 ... 768 ... 65535) <--- original list
# | | | |
# AA = (0 1 2 3 ... 255) <--- index list
(de index256 (L)
(make
(for (P L P (nth P 257))
(link P) ) ) )
(de nth256 (L N)
(nth L
(inc (/ N 256))
(inc (& 255 N)) ) )
(setq A (need 65536)) # original list
(setq AA (index256 A)) # index list
(de indexedAccess (N) # 50000 accesses to the N nth-element
(do 5000
(nth256 AA N) (nth256 AA N) (nth256 AA N) (nth256 AA N) (nth256 AA N)
(nth256 AA N) (nth256 AA N) (nth256 AA N) (nth256 AA N) (nth256 AA N) )
(bench (indexedAccess 50000)) gives 0.140 seconds (20 times slower)
So we have converted a 1300-times-slower access into a 20-times-slower
access.
--
UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
