enummapset merge into containers

[wren ng thornton]

On 2/21/12 3:58 PM, Ben Gamari wrote:
> In light of all of this, it was suggested by Edward Kmett that perhaps a
> HashMap would make sense. In my understanding, he proposed that the cost
> of hashing a short string could be dwarfed by the potential cache misses
> of a deep tree lookup. I haven't tested this hypothesis, but it seems
> plausible. Do you think this trade-off could make sense?

I'm in a similar situation for a natural language processing project. In 
my case I keep around a (HashMap,IntMap) bijection between strings and 
their integerization, and then have something like EnumMap which is used 
elsewhere since the Ints are newtyped. This approach has been more than 
fast enough for my needs; i.e., the performance bottlenecks are 
elsewhere so far as I can tell. I too often have to deal with pairs, 
triples, etc, of IDs--- but I need to do so with a trie's API so, alas, 
I can't use a HashMap for that part.

I don't think that giving out keys sequentially is the worst-case for 
IntMap[1].

In any case, I've been meaning to post my project to Hackage for about a 
year now. I was derailed a bit after I gave a talk about my EDSL for 
smoothing probability distributions and Ed Kmett asked me to factor it 
out into a separate package so he could use it. I've since broken the 
project up into a number of smaller more-reusable packages--- which is 
good in the long run, but I haven't had the time to put the pieces back 
together in order to post it to Hackage. Other than the smoothing EDSL, 
one of the packages is just for interning and integerizing strings. 
Since you're doing the same thing, we should talk off-list about API 
issues so that we can combine our work into a single package.


[1] At any given point all the allocated keys will form a compact 
subspace of Int which all share the high-order bits. Since IntMap is a 
big-endian trie with node-fusion, that means you'll have a complete tree 
for the low order bits and only one comparison for the long spine of all 
the high-order bits. The number of comparisons you need to make is 
always O(B) where B is the number of bits that differ among the 
subspace, but since the subspace is compact that means you're making the 
most-efficient use of the differing bits and so B = O(log N) where N is 
the number of allocated keys. In fact, this is one of the best cases for 
IntMap. The worst case is if you hand out keys in an order which 
maximizes B (e.g., handing out keys in an order like 
00000,10000,01000,00100,00010,...), since that means B will be min(N,W) 
where W is the word-size.

Any time you ensure that B = O(log N) it will be a best-case. For the 
case of sequential keys this amounts to having a complete tree, but for 
other cases it amounts to having an essentially complete tree ---where 
by "essential" we mean that the incompleteness always comes in long 
shared spines, such as the spine above the complete tree for the 
sequentially ordered case. If you gave out keys in the order (map 
bitwiseReverse [0..]) then you'd get an essentially-complete tree at the 
top, with long spines coming off for each of the leaves. You could also 
come up with other crazy orderings where you use, say, the top three and 
bottom three bits but hold the middle bits fixed.

The greater the number of discontiguous regions of variance the worse 
the performance will be, because even though we can still make it B = 
O(log N) we're increasing the constant factor since we have to do a 
comparison for each of the non-varying spines. Thus, [0..] or (map 
bitwiseReverse [0..]) are the best since they have only one non-varying 
spine. As described in the paper, Okasaki chose to use a big-endian trie 
instead of a little-endian trie because the constant factors are better 
for the [0..] case often used in projects that need to hand out unique 
IDs like machine learning, natural language processing, and compilers.

-- 
Live well,
~wren