[icinga-checkins] icinga.org: icinga-core/dev/cgis: core/classic ui: make hashfunc more efficient using sdbm #2761

git at icinga.org git at icinga.org
Wed Aug 1 03:00:26 CEST 2012


Module: icinga-core
Branch: dev/cgis
Commit: d96c8bb629e925a50f03762675ac5be7196732e9
URL:    https://git.icinga.org/?p=icinga-core.git;a=commit;h=d96c8bb629e925a50f03762675ac5be7196732e9

Author: Michael Friedrich <michael.friedrich at univie.ac.at>
Date:   Fri Jul  6 12:08:57 2012 +0200

core/classic ui: make hashfunc more efficient using sdbm #2761

currently, hashfunc runs in a loop adding up the characters.
this invokes a call to strlen on every run which is bad at once.
furthermore, the underlaying hash algorithm could cause collision
behaviour for similar keys.

               for (i = 0; i < strlen(name1); i++)
                       result += name1[i];

moving strlen before the loop helps a bit, but the hash algorithm needs
to be changed to be more effective once and for all.

the actual function is hash(i) = hash(i - 1) * 65599 + str[i]; which
leads to the magic constant of 65599 being a prime. berkely db and gawk
make use of that hash function as well.

http://www.cse.yorku.ca/~oz/hash.html

such enhancements will most likely only affect large scale systems with
a lot of similar keys, like one would generate with sni's
monitoring::testconfig module. either way, this should be adapted for
the core on comments/downtimes as well as statusdata, helping out the
classic ui scaling even better on reading the status data on each call.

props to Gunnar Beutner for finding and patching it.

refs #2761

---

 Changelog       |    9 +++++++++
 common/shared.c |   16 ++++++++++++----
 2 files changed, 21 insertions(+), 4 deletions(-)

diff --git a/Changelog b/Changelog
index 3f1bc89..e54f373 100644
--- a/Changelog
+++ b/Changelog
@@ -4,6 +4,15 @@ Icinga 1.7.x Change Log
 
 Thanks to all contributers, testers and developers. Please read AUTHORS and THANKS for a detailed list :-)
 
+1.8.0 - XX/10/2012
+
+ENHANCEMENTS
+* core/classic ui: make hashfunc more efficient by using sdbm #2761
+
+FIXES
+
+CHANGES
+
 1.7.1 - 18/06/2012
 
 FIXES
diff --git a/common/shared.c b/common/shared.c
index b62c407..692d305 100644
--- a/common/shared.c
+++ b/common/shared.c
@@ -353,6 +353,16 @@ void strip(char *buffer) {
 /**************************************************
  *************** HASH FUNCTIONS *******************
  **************************************************/
+static unsigned long sdbm(char *str) {
+	unsigned long hash = 0;
+	int c;
+
+	while ((c = *str++) != '\0')
+		hash = c + (hash << 6) + (hash << 16) - hash;
+
+	return hash;
+}
+
 /* dual hash function */
 int hashfunc(const char *name1, const char *name2, int hashslots) {
 	unsigned int i, result;
@@ -360,12 +370,10 @@ int hashfunc(const char *name1, const char *name2, int hashslots) {
 	result = 0;
 
 	if (name1)
-		for (i = 0; i < strlen(name1); i++)
-			result += name1[i];
+		result += sdbm(name1);
 
 	if (name2)
-		for (i = 0; i < strlen(name2); i++)
-			result += name2[i];
+		result += sdbm(name2);
 
 	result = result % hashslots;
 





More information about the icinga-checkins mailing list