1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
|
[[!meta copyright="Copyright © 2009, 2010, 2011, 2012, 2013, 2014 Free Software
Foundation, Inc."]]
[[!meta license="""[[!toggle id="license" text="GFDL 1.2+"]][[!toggleable
id="license" text="Permission is granted to copy, distribute and/or modify this
document under the terms of the GNU Free Documentation License, Version 1.2 or
any later version published by the Free Software Foundation; with no Invariant
Sections, no Front-Cover Texts, and no Back-Cover Texts. A copy of the license
is included in the section entitled [[GNU Free Documentation
License|/fdl]]."]]"""]]
[[!tag open_issue_hurd]]
* Hurd libihash
* old
* new
* hurd-l4 libhurd-ihash
# Open Issues
## Collisions
Viengoos: [[microkernel/viengoos/projects/new_hash_function]].
### IRC, freenode, #hurd, 2008/2009
<neal> so, we need a new ihash implementation
<neal> marcusb: When 80% full, the collision rate is very high.
<neal> marcusb: I tested using 512mb / 4096 entries
<neal> marcusb: Changing the load factor to 30% resulted in my program
running more than an order of magnitude faster.
<marcusb> yeah, it shouldn't get so full
<marcusb> don't we do an exponential back-off in the array size?
<marcusb> of course it's clear we can do much better
<marcusb> the ihash algo is very simple
<marcusb> I'm not even sure it makes much sense to have a generic
library
## Reader-Writer Locks
### IRC, freenode, #hurd, 2013-12-09
<teythoon> btw, why don't we use rwlocks for serializing access to our
hash tables ?
<braunr> teythoon: we definitely could
<teythoon> ok
<braunr> teythoon: we definitely could use rcu *whistles*
<teythoon> should we ?
<braunr> i don't know
<teythoon> yeah, ofc
<braunr> rwlocks have some overhead compared to mutexes
<braunr> and our mutexes are already quite expensive
<braunr> our condition variables are also not optimized
# [[community/gsoc/project_ideas/Object_Lookups]]
# Alternatives?
* glibc
* include/inline-hashtab.h
* locale/programs/simple-hash.h
* misc/hsearch_r.c
* NNS; cf. f46f0abfee5a2b34451708f2462a1c3b1701facd
* libstdc++: `unordered_map`, `tr1/unordered_map`, `ext/hash_map`
* libiberty: `hashtab.c`
* <http://cmph.sourceforge.net/>
* <http://libhashish.sourceforge.net/>
* <http://www.azillionmonkeys.com/qed/hash.html>
* CCAN's htable, idtree
* Not actually use a hashing data structure; see [[libports]], *Open Issues*,
*IRC, freenode, #hurd, 2013-11-14*.
|
