Mantis Bug Tracker

View Issue Details Jump to Notes ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0005292OCamlOCaml generalpublic2011-06-17 08:542012-09-25 20:10
Reporterart1 
Assigned To 
PrioritynormalSeverityminorReproducibilityalways
StatusclosedResolutionunable to reproduce 
PlatformOSOS Version
Product Version3.11.2 
Target VersionFixed in Version 
Summary0005292: Hashtbl.mem does not work with very complex keys
DescriptionHello,

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 InformationWe 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.
TagsNo tags attached.
Attached Files

- Relationships

-  Notes
(0006016)
xclerc (developer)
2011-06-20 09:10

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.
(0006017)
xleroy (administrator)
2011-06-20 18:59

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.
(0006437)
xleroy (administrator)
2011-12-21 12:01

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

- Issue History
Date Modified Username Field Change
2011-06-17 08:54 art1 New Issue
2011-06-20 09:10 xclerc Note Added: 0006016
2011-06-20 09:10 xclerc Status new => feedback
2011-06-20 18:59 xleroy Note Added: 0006017
2011-12-21 12:01 xleroy Note Added: 0006437
2011-12-21 12:01 xleroy Status feedback => resolved
2011-12-21 12:01 xleroy Resolution open => unable to reproduce
2012-09-25 20:10 xleroy Status resolved => closed


Copyright © 2000 - 2011 MantisBT Group
Powered by Mantis Bugtracker