[prev in list] [next in list] [prev in thread] [next in thread] 

List:       kfm-devel
Subject:    kjs math_object micro optimization?
From:       Luciano Montanaro <mikelima () virgilio ! it>
Date:       2003-05-19 10:34:28
[Download RAW message or body]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hi, I have been playing with the create_hash_table '-s' switch for the 
kjs classes, and I have found what I think is probably a typo in the math
object lookup table definition.
This is part of the output of the create_hash_table script for 
math_object.cpp:

Table: mathTable   26 entries

...

Hashsize: 17  Total Size: 28 Empty: 2 MaxDepth: 2 Collisions: 11
Hashsize: 18  Total Size: 29 Empty: 3 MaxDepth: 2 Collisions: 11
Hashsize: 19  Total Size: 32 Empty: 6 MaxDepth: 3 Collisions: 13
Hashsize: 20  Total Size: 32 Empty: 6 MaxDepth: 1 Collisions: 12
Hashsize: 21  Total Size: 33 Empty: 7 MaxDepth: 2 Collisions: 12
Hashsize: 22  Total Size: 34 Empty: 8 MaxDepth: 3 Collisions: 12
Hashsize: 23  Total Size: 32 Empty: 6 MaxDepth: 2 Collisions: 9
Hashsize: 24  Total Size: 33 Empty: 7 MaxDepth: 1 Collisions: 9
Hashsize: 25  Total Size: 34 Empty: 8 MaxDepth: 1 Collisions: 9
Hashsize: 26  Total Size: 35 Empty: 9 MaxDepth: 1 Collisions: 9
Hashsize: 27  Total Size: 35 Empty: 9 MaxDepth: 1 Collisions: 8
Hashsize: 28  Total Size: 36 Empty: 10 MaxDepth: 0 Collisions: 8
Hashsize: 29  Total Size: 37 Empty: 11 MaxDepth: 1 Collisions: 8
Hashsize: 30  Total Size: 38 Empty: 12 MaxDepth: 0 Collisions: 8
Hashsize: 31  Total Size: 34 Empty: 8 MaxDepth: 0 Collisions: 3
Hashsize: 32  Total Size: 42 Empty: 16 MaxDepth: 1 Collisions: 10

...

The math_object.cpp file defines an hash size of 21, and this is odd,
since it appears to be a quite bad choice, since it generates 12 collisions.
A better choice could be an hash size of 23, which could reduce memory usage
and number of collisions, or 31, which, at the cost of one additional entry in 
the table, reduces the collisions to only 3.

Did I miss something?

Luciano
- -- 
Luciano Montanaro// My public GPG key can be  /"\ ASCII RIBBON
               \X/ found at wwwkeys.pgp.net   \ /   CAMPAIGN
                                               X  AGAINST HTML 
                                              / \     MAIL
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.7 (GNU/Linux)

iD8DBQE+yLM7aeOY6B53J4URApCBAJ9SQB6jBCr7so+rxl40B1zzkAuuVACgiCQ5
avOinjMLzZVUNosiMSpJvoc=
=mhCD
-----END PGP SIGNATURE-----

["math_object.patch" (text/x-diff)]

Index: math_object.cpp
===================================================================
RCS file: /home/kde/kdelibs/kjs/math_object.cpp,v
retrieving revision 1.33
diff -u -r1.33 math_object.cpp
--- math_object.cpp	18 Apr 2003 08:29:49 -0000	1.33
+++ math_object.cpp	19 May 2003 10:28:13 -0000
@@ -44,7 +44,7 @@
 const ClassInfo MathObjectImp::info = { "Math", 0, &mathTable, 0 };
 
 /* Source for math_object.lut.h
-@begin mathTable 21
+@begin mathTable 31
   E             MathObjectImp::Euler    DontEnum|DontDelete|ReadOnly
   LN2           MathObjectImp::Ln2      DontEnum|DontDelete|ReadOnly
   LN10          MathObjectImp::Ln10     DontEnum|DontDelete|ReadOnly


[prev in list] [next in list] [prev in thread] [next in thread]