Ticket #4193 (closed proposal: fixed)
Add function to create new hashtables with a default size
| Reported by: | japple | Owned by: | simonmar |
|---|---|---|---|
| Priority: | high | Milestone: | 7.0.1 |
| Component: | libraries/base | Version: | 6.12.2 |
| Keywords: | hash, hash table | Cc: | |
| Operating System: | Unknown/Multiple | Architecture: | Unknown/Multiple |
| Type of failure: | None/Unknown | Difficulty: | |
| Test Case: | Blocked By: | ||
| Blocking: | Related Tickets: |
Description
In other some standard libraries (Java, OCaml), hash tables can be created with a use-supplied size. This avoids rehashing for users who know they will be inserting a lot of data.
Data.HashTable? does not expose a function to do this. This proposal changes that.
For a dictionary of 5 million strings, this patch saves me about 33% of the total execution time. For 10 million strings, this patch saves me 50% of the total execution time.
Attachments
-
hashtable_hint_size.dpatch
(43.1 KB) - added by japple
3 years ago.
- Initial proposed patch
-
Dict.hs
(0.9 KB) - added by japple
3 years ago.
- File for testing the patch with a hash table from strings to ()s
-
HashTable.hs
(18.3 KB) - added by japple
3 years ago.
- A full copy of Data.HashTable? with the patch applied and the module name changed (for ease of testing)
-
hashtable_hint_size_bittwiddle.dpatch
(43.4 KB) - added by japple
3 years ago.
- Patch version #2, changing size calculation to use bit twiddling
-
HashTable.2.hs
(18.2 KB) - added by japple
3 years ago.
- Version 2 of Data.HashTable? made for drop-in testing
Change History
Note: See
TracTickets for help on using
tickets.
