0005292: Hashtbl.mem does not work with very complex keys

View Issue Details [ Jump to Notes ]

[ Issue History ] [ Print ]

Project

Category

View Status

Date Submitted

Last Update

0005292

OCaml

OCaml general

public

2011-06-17 08:54

2012-09-25 20:10

Reporter

art1

Assigned To

Priority

normal

Severity

minor

Reproducibility

always

Status

closed

Resolution

unable to reproduce

Platform

OS Version

Product Version

3.11.2

Target Version

Fixed in Version

Summary

0005292: Hashtbl.mem does not work with very complex keys

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.

Tags

No 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