Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Hashtbl.mem does not work with very complex keys #5292

Closed
vicuna opened this issue Jun 17, 2011 · 3 comments
Closed

Hashtbl.mem does not work with very complex keys #5292

vicuna opened this issue Jun 17, 2011 · 3 comments
Labels

Comments

@vicuna
Copy link

vicuna commented Jun 17, 2011

Original bug ID: 5292
Reporter: art1
Status: closed (set by @xavierleroy on 2012-09-25T18:10:24Z)
Resolution: unable to duplicate
Priority: normal
Severity: minor
Version: 3.11.2
Category: ~DO NOT USE (was: OCaml general)
Monitored by: "Julien Signoles"

Bug description

Hello,

we have following data structure:

(** boundingbox, (x0,y0) means left down, (x1,y1) right upper edge )
type bbox_t = { x0 : int; y0 : int; x1 : int; y1 : int; }
type layer_t =
Background of (color_t
int)
| Foreground of color_t
| Garbage of color_t
| Unsegmented
type segm_t = {
s_layer: layer_t; (* layer of segment and it's color )
s_bboxes: bbox_t list; (
* pieces of segment, pair of kind of separation and bbox *)
s_frame: bbox_t;
}

(** segment, means a contigous area in a picture *)
type segment_t = Segment of segm_t

If we use segment_t as key in Hashtbl filling it via Hashtbl.replace, and try to find out if some segment_t's are member of that hash, the function Hashtbl.mem does not find that members.

But if we stringify the segment_t's the Hashtbl does work fine. The problem is hard to reproduce, because the error only occurs, if the bbox_t part is very large (5000-10000 entries).

Additional information

We are using Ocaml 3.11.2 because it is Debian Squeeze standard installation. If the error is fixed, it will be helpful to contact the debian maintainer to fix that, too.

Thanks for your help.

@vicuna
Copy link
Author

vicuna commented Jun 20, 2011

Comment author: @xclerc

I am afraid this is a known issue; you should take a look at the documentation
for "hash_param" on http://caml.inria.fr/pub/docs/manual-ocaml/libref/Hashtbl.html.
You should be able to overcome your problem by building a hash function with higher
values for "m" and "n". Notice that it would imply to switch to the functorial version, if
not already the case.

@vicuna
Copy link
Author

vicuna commented Jun 20, 2011

Comment author: @xavierleroy

I'd lvoe to have a repro case, even if it's big. xclerc is right that the default hash function performs poorly on long lists of bbox_t, but Hashtbl.replace and Hashtbl.mem should still work correctly, albeit slowly. So, we could have a real bug here, and the best way for us to find out is to be able to reproduce it.

@vicuna
Copy link
Author

vicuna commented Dec 21, 2011

Comment author: @xavierleroy

We are still unable to reproduce the issue, so I move to close it unless a repro case is provided.

@vicuna vicuna closed this as completed Sep 25, 2012
@vicuna vicuna added the bug label Mar 20, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

1 participant