From 11b74e38761fd04b8ca2bf9a85bb55fbf4d202ea Mon Sep 17 00:00:00 2001 From: Thomas Schwinge Date: Sun, 27 Sep 2009 23:08:39 +0200 Subject: Move Viengoos projects into separate per-project pages. --- microkernel/viengoos/projects/new_hash_function.mdwn | 19 +++++++++++++++++++ 1 file changed, 19 insertions(+) create mode 100644 microkernel/viengoos/projects/new_hash_function.mdwn (limited to 'microkernel/viengoos/projects/new_hash_function.mdwn') diff --git a/microkernel/viengoos/projects/new_hash_function.mdwn b/microkernel/viengoos/projects/new_hash_function.mdwn new file mode 100644 index 00000000..1747511d --- /dev/null +++ b/microkernel/viengoos/projects/new_hash_function.mdwn @@ -0,0 +1,19 @@ +[[!meta copyright="Copyright © 2008, 2009 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_viengoos]] + +The current hash function in libhurd-ihash results in a lot of +collisions when the hash table is 80% full. To overcome this, we keep +hash tables at most 30% full. This represents a fair amount of +overhead. Find a better algorithm. There can either be one that is +appropriate in the general case or one that works well in a relevant, +specific case, e.g., viengoos/object.c uses a hash to find the object +corresponding to a frame, which is keyed on its physical address. -- cgit v1.2.3 From 49ba9b1409a9c36d9d1019c74afc7b5e8d3c5d84 Mon Sep 17 00:00:00 2001 From: Thomas Schwinge Date: Fri, 30 Jul 2010 16:45:14 +0200 Subject: Add links between hurd/libihash and microkernel/viengoos/projects/new_hash_function. --- hurd/libihash.mdwn | 23 +++++++++++----------- .../viengoos/projects/new_hash_function.mdwn | 5 ++++- 2 files changed, 16 insertions(+), 12 deletions(-) (limited to 'microkernel/viengoos/projects/new_hash_function.mdwn') diff --git a/hurd/libihash.mdwn b/hurd/libihash.mdwn index 39692939..770770c7 100644 --- a/hurd/libihash.mdwn +++ b/hurd/libihash.mdwn @@ -8,9 +8,19 @@ 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]]."]]"""]] - * IRC, unknown channel, unknown date +[[!tag open_issue_hurd]] - [[!tag open_issue_hurd]] + * Hurd libihash + + * old + + * new + + * hurd-l4 libhurd-ihash + + * [[viengoos libhurd-ihash|microkernel/viengoos/projects/new_hash_function]] + + IRC, unknown channel, unknown date so, we need a new ihash implementation marcusb: When 80% full, the collision rate is very high. @@ -22,15 +32,6 @@ is included in the section entitled the ihash algo is very simple I'm not even sure it makes much sense to have a generic library - * Hurd libihash - - * old - - * new - - * hurd-l4 libhurd-ihash - - * viengoos libhurd-ihash # Alternatives? diff --git a/microkernel/viengoos/projects/new_hash_function.mdwn b/microkernel/viengoos/projects/new_hash_function.mdwn index 1747511d..d0374720 100644 --- a/microkernel/viengoos/projects/new_hash_function.mdwn +++ b/microkernel/viengoos/projects/new_hash_function.mdwn @@ -1,4 +1,5 @@ -[[!meta copyright="Copyright © 2008, 2009 Free Software Foundation, Inc."]] +[[!meta copyright="Copyright © 2008, 2009, 2010 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 @@ -17,3 +18,5 @@ overhead. Find a better algorithm. There can either be one that is appropriate in the general case or one that works well in a relevant, specific case, e.g., viengoos/object.c uses a hash to find the object corresponding to a frame, which is keyed on its physical address. + +Note that this applies to the Hurd's [[hurd/libihash]], too. -- cgit v1.2.3