Stackoverflow with specialized Hashtbl (via Hashtbl.make)

Question

I am using this piece of code and stackoverflow will be launched, if I use Extlib Hashtbl, an error does not occur. Any tips for using a specialized hashtbl without stackoverflow?

module ColorIdxHash = Hashtbl.Make( struct type t = Img_types.rgb_t let equal = (==) let hash = Hashtbl.hash end ) (* .. *) let (ctable: int ColorIdxHash.t) = ColorIdxHash.create 256 in for x = 0 to width -1 do for y = 0 to height -1 do let c = Img.get img xy in let rgb = Color.rgb_of_color c in if not (ColorIdxHash.mem ctable rgb) then ColorIdxHash.add ctable rgb (ColorIdxHash.length ctable) done done; (* .. *) 

The return points to hashtbl.ml:

Fatal error: exception Stack_overflow Raised in the file "hashtbl.ml", line 54, characters 16-40 Called from the file "img / write_bmp.ml", line 150, characters 52-108 ...

Any clues?

Answer 1

Well, you use physical equality (==) to compare colors in your hash table. If the colors are structured values ​​(I cannot say from this code), none of them will be physically equal to each other. If all the colors are separate objects, they will all go into a table, which really can be quite a large number of objects. On the other hand, the hash function will be based on the actual color values ​​of R, G, B, so there may well be a large number of duplicates. This will mean that your hash buckets will have very long chains. Perhaps some internal function is not tail recursive, so it overflows the stack.

Usually the length of the longest chain will be 2 or 3, so it is not surprising that this error does not occur often.

Looking at my copy of hashtbl.ml (OCaml 3.12.1), I don't see anything non-tail-recursive on line 54. So my hunch might be wrong. At line 54, a new internal array is allocated for the hash table. So, another idea is that your hash table just gets too big (possibly due to unwanted duplicates).

You can try to use structural equality (=) and see if the problem persists.

Answer 2

One of the reasons you might have stack overflows or stack overflows is because your type contains circular values. (==) will end in cyclic values ​​(while (=) may not match), but Hash.hash is probably not safe for the loop. Therefore, if you are manipulating cyclic values ​​like Img_types.rgb_t , you need to develop your one-cylinder hash function - usually by calling Hash.hash on only one of the non-cyclic subfields / subcomponents of your values.

I have already been bitten by this very issue in the past. Not a fun bug to track.