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

List:       kde-bugs-dist
Subject:    [Bug 191182] VALGRIND_LEAK_CHECK quadratic when big nr of chunks or
From:       <philippe.waroquiers () eurocontrol ! int>
Date:       2009-05-01 6:56:04
Message-ID: 20090501065604.4CA2016437 () immanuel ! kde ! org
[Download RAW message or body]

https://bugs.kde.org/show_bug.cgi?id=191182





--- Comment #5 from  <philippe waroquiers eurocontrol int>  2009-05-01 08:55:57 ---
(2nd trial to send this comment, 1st failed)

I thought about the sort chunks solution before implementing the HT.

The cost of the sort based will be:
  n log n  cmp for the sort
  n        cmp for the merge

Assuming the hash function is good, the nr of collisions should be low.
So, we have about n cmp for the hash table.
It might be worth adding in the debuglog of hash table an output of
the nr of collisions (e.g. in the debug log of the resize operation).

As I found the HT code elegant and quite easy to modify, I went that way.
Also, at work, we are calling LEAK search a high nr of times (about 5000)
with millions of chunks allocated. So, the HT looked better.
But I do not know if the theoretical reasoning is correct.

-- 
Configure bugmail: https://bugs.kde.org/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are watching all bug changes.
[prev in list] [next in list] [prev in thread] [next in thread]