On 11/2/22 01:28, Carlos wrote:
> I don't know what a sparse array is in this context.
Thanks for your feedback and thoughts.
I deliberately chose a term that suggests the implementation without
pinning it down so that I could ask about speed vs space without getting
bogged down over how it was implemented.
Here's how I implemented it:
A "sparse" array contains values indexed by integers, and efficiently
permits missing values. Each element in the array is a sub-array
containing the index of the first value followed by one or more values.
For example: [[8 v8 v9 v10] [14 v14 v15] [37 v37]] is a sparse array
containing values at index 8, 9, 10, 14, 15 and 37.
The sparseget procedure retrieves an element from a sparse array. If
the array contains a value at that index, the value and true is pushed
on the stack, otherwise false is pushed.
I compared normal versus packed arrays and found that packing saved
negligible space while substantially increasing access time, so sparse
arrays are not packed.
In terms of performance versus a dictionary (for UnicodeEncoding map)
accessing a sparse array takes around 5 times longer, which sounds awful
but (on my computer) that's sub-1ns access versus 4ns, so I don't think
the speed is an issue.
One inexplicable result is that the sparse array generated from the
built-in AdobeGlyphList (Ghostscript 9.50 on Ubuntu 20.04 with Intel
i7-1165G7 @ 2.80Mhz) takes 25 times as long as the equivalent
dictionary. I don't understand why so much slower compared with maps
from fonts. Clutching at straws, I initially thought it might be
because AdobeGlyphList is built-in and maps from (non-builtin) fonts
aren't, but that can't be the case. For benchmarks, I load the
dictionary and sparse arrays from external files so, although derived
from the built-in dictionary, they are unlikely to be stored in common.
I also tried changing the names (added "xx" to them) and the result
stands. It's a mystery to me.
I'm inclined to go for space over speed but am willing to listen to
reason if people feel strongly that speed is more important.