[scala] Open versus Chained HashMap
|
View:
New views
11 Messages
—
Rating Filter:
Alert me
|
 |
[scala] Open versus Chained HashMap
by Ismael Juma-3
::
Rate this Message:
Hi,
OpenHashMap from David MacIver was recently introduced to the Scala library and it seems to perform much better than the existing mutable.HashMap. It uses open addressing, but with wrapper Entry objects. This is a bit unconvential since one of the main advantages of open addressing versus chaining is that it does not require wrapper objects, saving memory and reducing indirection. David has told me that the alternative of having separate arrays for keys, values and (optionally) hashes was substantially slower. Given that, chaining should not impose much more overhead (just an additional reference in each Entry object) and could even result in lower memory usage if one takes into account that chained implementations perform relatively well with higher load factors (typically 0.75 instead of 0.50 for open addressing). So, I decided to create a ChainedHashMap starting from OpenHashMap and test the theory. Given the tests and benchmarks that David wrote for his implementations, it seemed easy enough. :) After getting all of David's tests to pass, I ran the benchmarks with 3 different variations for ChainedHashMap: - ChainedHashMap (the default): load factor of 0.75 and resize multiplier of 2 - ChainedHashMap medium: load factor of 0.65 and resize multiplier of 2. - ChainedHashMap large: load factor of 0.50 and resize multiplier of 2. This is the same as OpenHashMap, so with this configuration ChainedHashMap has an additional reference for each entry and the internal array would always be of the same size. The benchmark used 5000 entries which results in an additional 39KB in a 64-bit machine (half in a 32-bit one or a 64-bit JVM with compressed references). For the other configurations, depending on how much smaller the resulting array is, it's possible for chaining to use less memory. On my machine with JDK6u10 -server and a large heap, the ChainedHashMap performs the same or better in every test (test results attached). The actual difference in every test varied depending on which configuration. With the exception of foreach, the difference was not dramatic in any test but it was still noticeable for get. The "large" configuration performs better in update and get, but worse in iteration as expected. In order to show the kind of difference one can expect by using a different load and resize factor, the size of the internal array of the maps after the 5000 items were inserted was (this of course varies with different sizes): OpenHashMap array length 16384 ChainedHashMap array length 8192 ChainedHashMap medium array length 8192 ChainedHashMap large array length 16384 >From this specific set of tests, it seems to me that one can achieve slightly better performance with slightly less memory usage by using chaining with the default configuration presented above. It's not a complete set of tests by any means, but do people see any advantage in using open addressing with wrapper Entry objects versus chaining? Regards, Ismael P.S. As usual there might be bugs that affect the results above, hopefully David's map tests have good coverage though. :) Number of items in maps (with the exception of update): 4999 OpenHashMap array length 16384 ChainedHashMap array length 8192 ChainedHashMap medium array length 8192 ChainedHashMap large array length 16384 Mutable HashMap: update Jcl Hashmap: update OpenHashMap: update ChainedHashMap: update ChainedHashMap medium: update ChainedHashMap large: update ----------------------------------------------------------------------------------------------------------------------------------------------------------- 2491 413 379 364 348 301 1181 368 358 356 337 294 ----------------------------------------------------------------------------------------------------------------------------------------------------------- 1173 366 351 353 341 296 1174 367 355 355 335 296 1173 365 350 349 340 291 1173 367 353 346 337 291 1172 375 350 347 339 292 1172 366 355 347 340 296 1170 366 353 346 332 304 1171 365 349 348 334 291 1186 366 350 350 334 291 1210 367 351 348 334 291 ----------------------------------------------------------------------------------------------------------------------------------------------------------- 1177 ms 367 ms 352 ms 349 ms 337 ms 294 ms 0 M/s 0 M/s 0 M/s 0 M/s 0 M/s 0 M/s 100 % 320 % 334 % 337 % 349 % 400 % ----------------------------------------------------------------------------------------------------------------------------------------------------------- JCL HashMap: get OpenHashMap ChainedHashMap ChainedHashMap medium ChainedHashMap large ----------------------------------------------------------------------------------------------- 326 298 266 262 227 300 285 252 252 215 ----------------------------------------------------------------------------------------------- 299 296 252 252 216 304 290 255 256 220 304 288 254 259 221 305 289 259 261 218 313 295 257 257 224 302 290 255 257 220 308 294 277 274 230 319 305 257 258 225 305 284 218 218 182 299 285 219 218 182 ----------------------------------------------------------------------------------------------- 306 ms 291 ms 250 ms 251 ms 214 ms 0 M/s 0 M/s 0 M/s 0 M/s 0 M/s 100 % 104 % 122 % 121 % 142 % ----------------------------------------------------------------------------------------------- Mutable HashMap: apply JCL HashMap: apply JCL HashMap: apply OpenHashMap: apply ChainedHashMap: apply ChainedHashMap medium: apply ChainedHashMap large: apply ------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 826 195 194 169 166 167 152 808 184 183 162 161 163 148 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 813 183 183 162 161 171 151 813 185 183 162 161 163 148 814 181 183 161 161 162 147 812 181 187 161 161 162 147 811 181 182 161 161 162 147 824 185 184 161 162 167 148 812 181 182 161 161 162 147 816 193 183 161 161 166 148 818 184 182 166 161 156 142 819 185 182 158 161 155 143 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 815 ms 184 ms 183 ms 161 ms 161 ms 163 ms 147 ms 0 M/s 0 M/s 0 M/s 0 M/s 0 M/s 0 M/s 0 M/s 100 % 442 % 444 % 503 % 505 % 500 % 553 % ------------------------------------------------------------------------------------------------------------------------------------------------------------------------- TreeHashMap: foreach HashMap: foreach JCL HashMap: foreach OpenHashMap: foreach ChainedHashMap: foreach ChainedHashMap medium: foreach ChainedHashMap large: foreach ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 184 570 228 319 160 150 181 173 554 217 311 149 147 182 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 172 550 219 313 152 147 185 172 554 225 314 149 149 179 175 555 224 310 155 153 181 174 552 222 311 148 149 183 177 552 222 310 148 145 179 172 550 222 312 149 146 182 177 559 226 310 148 146 179 177 552 233 310 148 151 182 171 556 219 313 149 149 179 172 549 219 276 156 157 183 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 174 ms 553 ms 223 ms 308 ms 150 ms 149 ms 181 ms 0 M/s 0 M/s 0 M/s 0 M/s 0 M/s 0 M/s 0 M/s 100 % 31 % 78 % 56 % 115 % 116 % 95 % ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- TreeHashMap: elements.foreach HashMap: elements.foreach JCL HashMap: elements.foreach OpenHashMap: elements.foreach ChainedHashMap: elements.foreach ChainedHashMap medium: elements.foreach ChainedHashMap large: elements.foreach ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 376 561 223 278 225 202 233 344 576 217 256 200 198 218 ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 323 563 216 257 197 197 229 332 571 221 258 203 151 175 329 566 218 259 153 157 178 324 561 217 261 153 151 172 324 553 217 255 151 154 175 324 562 217 255 152 151 170 325 554 218 254 152 150 169 332 518 219 264 157 156 174 268 519 198 197 151 153 171 269 514 174 198 151 151 171 ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 315 ms 548 ms 211 ms 246 ms 162 ms 157 ms 178 ms 0 M/s 0 M/s 0 M/s 0 M/s 0 M/s 0 M/s 0 M/s 100 % 57 % 148 % 128 % 194 % 200 % 176 % ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
|
|
Re: [scala] Open versus Chained HashMap
by David MacIver
::
Rate this Message:
On Mon, Sep 1, 2008 at 2:33 PM, Ismael Juma <ismaelj@...> wrote:
> Hi, > > OpenHashMap from David MacIver was recently introduced to the Scala > library and it seems to perform much better than the existing > mutable.HashMap. It uses open addressing, but with wrapper Entry > objects. This is a bit unconvential since one of the main advantages of > open addressing versus chaining is that it does not require wrapper > objects, saving memory and reducing indirection. David has told me that > the alternative of having separate arrays for keys, values and > (optionally) hashes was substantially slower. Given that, chaining My theory is that this is because it increases the number of bounds checks the JVM inserts dramatically. Presumably it also decreases locality of reference (in a way that storing them inline in the array wouldn't), but I'm not sure about this point. > should not impose much more overhead (just an additional reference in > each Entry object) and could even result in lower memory usage if one > takes into account that chained implementations perform relatively well > with higher load factors (typically 0.75 instead of 0.50 for open > addressing). > > So, I decided to create a ChainedHashMap starting from OpenHashMap and > test the theory. Given the tests and benchmarks that David wrote for his > implementations, it seemed easy enough. :) Glad they proved useful. :-) > After getting all of David's tests to pass, I ran the benchmarks with 3 > different variations for ChainedHashMap: > > - ChainedHashMap (the default): load factor of 0.75 and resize > multiplier of 2 > > - ChainedHashMap medium: load factor of 0.65 and resize multiplier of 2. > > - ChainedHashMap large: load factor of 0.50 and resize multiplier of 2. > This is the same as OpenHashMap, so with this configuration > ChainedHashMap has an additional reference for each entry and the > internal array would always be of the same size. The benchmark used 5000 > entries which results in an additional 39KB in a 64-bit machine (half in > a 32-bit one or a 64-bit JVM with compressed references). For the other > configurations, depending on how much smaller the resulting array is, > it's possible for chaining to use less memory. > > On my machine with JDK6u10 -server and a large heap, the ChainedHashMap > performs the same or better in every test (test results attached). The > actual difference in every test varied depending on which configuration. > With the exception of foreach, the difference was not dramatic in any > test but it was still noticeable for get. The "large" configuration > performs better in update and get, but worse in iteration as expected. > > In order to show the kind of difference one can expect by using a > different load and resize factor, the size of the internal array of the > maps after the 5000 items were inserted was (this of course varies with > different sizes): > > OpenHashMap array length 16384 > ChainedHashMap array length 8192 > ChainedHashMap medium array length 8192 > ChainedHashMap large array length 16384 > > >From this specific set of tests, it seems to me that one can achieve > slightly better performance with slightly less memory usage by using > chaining with the default configuration presented above. It's not a > complete set of tests by any means, but do people see any advantage in > using open addressing with wrapper Entry objects versus chaining? In theory the probing scheme I used may be more resilient to bad hashes. I don't have a test case to prove this though. :-) Certainly if your implementation proves better in the generic case I don't see any reason it shouldn't be used in preference to mine. Is the source available anywhere? I'd be interested to take a look. > Regards, > Ismael > > P.S. As usual there might be bugs that affect the results above, > hopefully David's map tests have good coverage though. :) The coverage on OpenHashMap should be pretty good, as I specifically threw lots of tests at it to pin down a class of bugs that was troubling me. :-) |
|
|
Re: [scala] Open versus Chained HashMap
by Ismael Juma-3
::
Rate this Message:
On Mon, 2008-09-01 at 14:52 +0100, David MacIver wrote:
> > David has told me that > > the alternative of having separate arrays for keys, values and > > (optionally) hashes was substantially slower. Given that, chaining > > My theory is that this is because it increases the number of bounds > checks the JVM inserts dramatically. Presumably it also decreases > locality of reference (in a way that storing them inline in the array > wouldn't), but I'm not sure about this point. Right, I thought about that, but in theory using Entry objects does not provide better locality of reference since it just contains references anyway. But maybe the JVM is doing something that causes better locality of reference for Entry objects because it seemed to me that the additional bounds checks should not cause the kind of disparity that you saw. Storing everything in a single array would be interesting and it's what IdentityHashMap in the JDK does. As you know, IdentityHashMap needs to solve a more restricted problem. They can rely on linear probing because reference hashCodes in HotSpot have good distribution and are also cheap to compute (so no need to cache them). > In theory the probing scheme I used may be more resilient to bad > hashes. I don't have a test case to prove this though. :-) I don't understand why this is so. Note that ChainedHashMap uses the same hashOf method as OpenHashMap, but it does not need to probe because of the chaining nature. > Is the source available anywhere? I'd be interested to take a look. I am attaching it. Note I basically started from OpenHashMap and modified it until it was using chaining and it passed the tests in order to benchmark it. I haven't cleaned it up since, so things might be a bit ugly. ;) Ismael package scala.collection.mutable; object ChainedHashMap{ def apply[K, V](elems : (K, V)*) = { val dict = new ChainedHashMap[K, V]; elems.foreach({case (x, y) => dict(x) = y}); dict; } private[mutable] class Entry[Key, Value](val key : Key, val hash : Int, var value : Option[Value], var next: Entry[Key, Value]) private[mutable] def highestOneBit(j : Int) = { // This should really go somewhere central as we're now code sharing by cut and paste. :( var i = j; i |= (i >> 1); i |= (i >> 2); i |= (i >> 4); i |= (i >> 8); i |= (i >> 16); i - (i >>> 1); } private[mutable] def nextPowerOfTwo(i : Int) = highestOneBit(i) << 1; } import ChainedHashMap.Entry; class ChainedHashMap[Key, Value](initialSize : Int, loadFactor: Double, resizeMultiplier: Int) extends scala.collection.mutable.Map[Key, Value]{ def this(initialSize: Int) = this(initialSize, 0.75, 2); def this() = this(8) private[this] val actualInitialSize = ChainedHashMap.nextPowerOfTwo(initialSize); private var mask = actualInitialSize - 1;; private var table : Array[Entry[Key, Value]] = new Array[Entry[Key, Value]](actualInitialSize); private var _size = 0; // Used for tracking inserts so that iterators can determine in concurrent modification has occurred. private[this] var modCount = 0; def size = _size; private[this] def size_=(s : Int) = _size = s; protected def hashOf(key : Key) = { var h = key.hashCode; h ^= ((h >>> 20) ^ (h >>> 12)); h ^ (h >>> 7) ^ (h >>> 4); h } private[this] def growTable = { val oldSize = mask + 1; val newSize = resizeMultiplier * oldSize; val oldTable = table; table = new Array[Entry[Key, Value]](newSize); mask = newSize - 1; var i = 0 while (i < oldSize) { var entry = oldTable(i) while (entry != null) { val next = entry.next val newIndex = findIndex(entry.hash) entry.next = table(newIndex) table(newIndex) = entry entry = next } i += 1 } } def getArrayLength = table.size private[this] def findIndex(key : Key) : Int = findIndex(hashOf(key)); private[this] def findIndex(hash : Int) : Int = { hash & mask } def update(key : Key, value : Value){ update(key, hashOf(key), value); } private def update(key : Key, hash : Int, value : Value) { if (size > mask * loadFactor) growTable; val index = findIndex(hash); val entry = table(index); if (entry == null) { table(index) = new Entry(key, hash, Some(value), null); modCount += 1; size += 1; } else { var e = entry; while(e != null){ if (e.hash == hash && e.key == key){ e.value = Some(value); return; } e = e.next } table(index) = new Entry(key, hash, Some(value), entry) modCount += 1; size += 1; } } def -=(key : Key) { val hash = hashOf(key) val index = findIndex(hash); var previous = table(index) var entry = previous while(entry != null){ val next = entry.next if (entry.hash == hash && entry.key == key){ size -= 1 if (previous == entry) table(index) = next else previous.next = next return } else { previous = entry entry = next } } } def get(key : Key) : Option[Value] = { val hash = hashOf(key); var entry = table(findIndex(hash)); while(entry != null){ if (entry.hash == hash && entry.key == key){ return entry.value; } entry = entry.next } None; } /** * An iterator over the elements of this map. Use of this iterator follows the same * contract for concurrent modification as the foreach method. */ def elements = new Iterator[(Key, Value)]{ var index = 0; var nextEntry: Entry[Key, Value] = _ val initialModCount = modCount; if (size > 0) advanceInTable(); private[this] def advanceInTable() { var i = 0 while (index < table.length) { nextEntry = table(index) index += 1 i += 1 if (nextEntry != null) return } } private[this] def advance() { if (initialModCount != modCount) error("Concurrent modification"); if (nextEntry == null) throw new NoSuchElementException() nextEntry = nextEntry.next if (nextEntry == null) advanceInTable() } def hasNext = (nextEntry != null) def next() = { val result = nextEntry; advance; (result.key, result.value.get); } } override def clone : ChainedHashMap[Key, Value] = { val it = new ChainedHashMap[Key, Value] foreachUndeletedEntry(entry => it.update(entry.key, entry.hash, entry.value.get)); it } /** * Loop over the key, value mappings of this map. * * The behaviour of modifying the map during an iteration is as follows: * * <ul> * <li>Deleting a mapping is always permitted.</li> * <li>Changing the value of mapping which is already present is permitted.</li> * <li>Anything else is not permitted. It will usually, but not always, throw an exception.</li> * </ul> * * @param f The function to apply to each key, value mapping. */ override def foreach(f : ((Key, Value)) => Unit){ val startModCount = modCount; foreachUndeletedEntry(entry => { if (modCount != startModCount) error("Concurrent Modification") f((entry.key, entry.value.get))} ); } private[this] def foreachUndeletedEntry(f : Entry[Key, Value] => Unit){ var i = 0 while (i < table.length) { var entry = table(i) while(entry != null){ f(entry) entry = entry.next } i += 1 } } override def transform(f : (Key, Value) => Value) = foreachUndeletedEntry(entry => entry.value = Some(f(entry.key, entry.value.get))); /* override def retain(f : (Key, Value) => Boolean) = { var i = 0 while (i < mask) { val entry = table(i) if (entry != null && if (!f(entry.key, entry.value.get) } } */ override def stringPrefix = "ChainedHashMap" } |
|
|
Re: [scala] Open versus Chained HashMap
by David Pollak
::
Rate this Message:
Ismael Juma wrote: My understanding of the JVM is that objects are far better optimized than arrays.On Mon, 2008-09-01 at 14:52 +0100, David MacIver wrote:
|
|
|
Re: [scala] Open versus Chained HashMap
by David MacIver
::
Rate this Message:
On Mon, Sep 1, 2008 at 3:24 PM, Ismael Juma <ismaelj@...> wrote:
> On Mon, 2008-09-01 at 14:52 +0100, David MacIver wrote: >> > David has told me that >> > the alternative of having separate arrays for keys, values and >> > (optionally) hashes was substantially slower. Given that, chaining >> >> My theory is that this is because it increases the number of bounds >> checks the JVM inserts dramatically. Presumably it also decreases >> locality of reference (in a way that storing them inline in the array >> wouldn't), but I'm not sure about this point. > > Right, I thought about that, but in theory using Entry objects does not > provide better locality of reference since it just contains references > anyway. But maybe the JVM is doing something that causes better I had a convincing reason why it might happen, but I'm no longer sure what it was. It might be related to the position of the Entry objects. Given that they're all freshly allocated in the current thread local allocation block, most of them might still be in cache? > locality of reference for Entry objects because it seemed to me that > the additional bounds checks should not cause the kind of disparity > that you saw. Storing everything in a single array would be interesting I don't know. It wasn't an utterly dramatic slowdown, and on fairly fast operations. Tripling the number of tests inside the lookup could easily be a significant hit. > and it's what IdentityHashMap in the JDK does. As you know, The problem I had with this is that it would then require either non-caching of the hash codes or boxing of the hash keys, so in the former case it's potentially dramatically slower and in the latter it wouldn't really decrease the memory use. Non-caching hash codes could at least be interesting to experiment with, as it works well with some cases (ints, strings, umm... basically nothing else. :-) ). Hm. Actually, you don't need to recompute the hash of the keys already in the table. Currently the hash for them *is* used, but only because it's cheap to do so. If that was removed it would result in more expensive equality tests within the map but lower memory usage and less indirection. Worth a go, certainly. > IdentityHashMap needs to solve a more restricted problem. They can rely on > linear probing because reference hashCodes in HotSpot have good > distribution and are also cheap to compute (so no need to cache them). Right. >> In theory the probing scheme I used may be more resilient to bad >> hashes. I don't have a test case to prove this though. :-) > > I don't understand why this is so. Note that ChainedHashMap uses the > same hashOf method as OpenHashMap, but it does not need to probe because > of the chaining nature. The function chosen for probing is done in a way that can result in very short probes where in principle you might end up with much longer chains in the chaining. Like I said, I don't have a test case that demonstrates this, so I could be totally wrong. :-) |
|
|
Re: [scala] Open versus Chained HashMap
by Ismael Juma-3
::
Rate this Message:
On Mon, 2008-09-01 at 15:39 +0100, David MacIver wrote:
> On Mon, Sep 1, 2008 at 3:24 PM, Ismael Juma <ismaelj@...> wrote: > > Right, I thought about that, but in theory using Entry objects does not > > provide better locality of reference since it just contains references > > anyway. But maybe the JVM is doing something that causes better > > I had a convincing reason why it might happen, but I'm no longer sure > what it was. <some possible reasons snipped> Yes, I think they're plausible, but hard to know for sure without some lower-level profiling tools. > > and it's what IdentityHashMap in the JDK does. As you know, > > The problem I had with this is that <...> Yes, it's not clear if it's a win, but as you say might be worth a shot. > >> In theory the probing scheme I used may be more resilient to bad > >> hashes. I don't have a test case to prove this though. :-) > > > > I don't understand why this is so. Note that ChainedHashMap uses the > > same hashOf method as OpenHashMap, but it does not need to probe because > > of the chaining nature. > > The function chosen for probing is done in a way that can result in > very short probes where in principle you might end up with much longer > chains in the chaining. > > Like I said, I don't have a test case that demonstrates this, so I > could be totally wrong. :-) Oh I see. Interesting. Ismael |
|
|
Re: [scala] Open versus Chained HashMap
by Erik Engbrecht
::
Rate this Message:
re: Identity hash codes
IIRC identity hash codes are effectively cached by the JVM...I think they're in the object header or something like that. This needs to be done so that the hash code doesn't change from one invocation to another. If you want a stable hash code, it either has to be based on something that won't change or once it is computed it has to be stored, so it becomes the thing that won't change. Remember, Java objects move around in memory, so you can't use the physical address as a stable value. You have to store something.
So you don't need to cache the value of identity hash code because the JVM is already doing it, not simply because it is cheap to compute (in fact initially computing and storing it requires some synchronization, so initial computation might not even been "cheap" for some definition of "cheap").
On Mon, Sep 1, 2008 at 10:39 AM, David MacIver <david.maciver@...> wrote:
-- http://erikengbrecht.blogspot.com/ |
|
|
Re: [scala] Open versus Chained HashMap
by Ismael Juma-3
::
Rate this Message:
On Mon, 2008-09-01 at 11:19 -0400, Erik Engbrecht wrote:
> re: Identity hash codes > IIRC identity hash codes are effectively cached by the JVM. Right, I know that[1]. I used the term compute too loosely and one could say it was misleading. The point was simply that storing the hash in the Map requires it to be computed once anyway, and subsequent invocations are cheap enough (due to the caching as you say) that it's not worth caching it in the Map itself. Ismael [1] That was one of the positive side-effects of the "Is Scala for Academics and Egomaniacs" incident. ;) |
|
|
Re: [scala] Open versus Chained HashMap
by Erik Engbrecht
::
Rate this Message:
Academics, egomaniacs, and people who will readily dig into JVM source code to prove a point.
At least something good came of that incident. On Mon, Sep 1, 2008 at 11:30 AM, Ismael Juma <ismaelj@...> wrote:
-- http://erikengbrecht.blogspot.com/ |
|
|
Re: [scala] Open versus Chained HashMap
by David MacIver
::
Rate this Message:
On Mon, Sep 1, 2008 at 3:39 PM, David MacIver <david.maciver@...> wrote:
> Non-caching hash codes could at least be interesting to experiment > with, as it works well with some cases (ints, strings, umm... > basically nothing else. :-) ). > > Hm. Actually, you don't need to recompute the hash of the keys already > in the table. Currently the hash for them *is* used, but only because > it's cheap to do so. If that was removed it would result in more > expensive equality tests within the map but lower memory usage and > less indirection. Worth a go, certainly. I tried this. It seemed to be slower. This might be because I'm currently doing a little too much computation for the indexing, but I really couldn't be bothered to experiment further. :-) |
|
|
Re: [scala] Open versus Chained HashMap
by Ismael Juma-3
::
Rate this Message:
Hi David,
We discussed in the past whether it was worth changing Entry.value to be of type Value instead of Option[Value]. The main advantage of this is lower memory overhead. I was curious what effect the additional allocation on get and the reduced indirection would have though. So I changed the ChainedHashMap and made sure to override apply to avoid the unnecessary allocation. The test results were quite good (attached). Updates were about 10% faster, apply was the same, foreach slightly faster (but could be just noise) and gets were about the same expect for the two last runs. For some reason, before the change the two last runs for get were noticeable faster (218 and 219 versus around 250 for all the other warm ones). Might be worth exploring for OpenHashMap even though it's a bit more complicated there due to the lazy deletion algorithm currently used (as you told me). Regards, Ismael (in /home/ijuma/src/drmacivermisc/scala/stuff) warning: there were deprecation warnings; re-run with -deprecation for details one warning found Number of items in map: 4999 OpenHashMap array length 16384 ChainedHashMap array length 8192 ChainedHashMap medium array length 8192 ChainedHashMap large array length 16384 Number of items in map: 4999 OpenHashMap array length 16384 ChainedHashMap array length 8192 ChainedHashMap medium array length 8192 ChainedHashMap large array length 16384 Number of items in map: 4999 OpenHashMap array length 16384 ChainedHashMap array length 8192 ChainedHashMap medium array length 8192 ChainedHashMap large array length 16384 Number of items in map: 4999 OpenHashMap array length 16384 ChainedHashMap array length 8192 ChainedHashMap medium array length 8192 ChainedHashMap large array length 16384 Number of items in map: 4999 OpenHashMap array length 16384 ChainedHashMap array length 8192 ChainedHashMap medium array length 8192 ChainedHashMap large array length 16384 Mutable HashMap: update Jcl Hashmap: update OpenHashMap: update ChainedHashMap: update ChainedHashMap medium: update ChainedHashMap large: update ----------------------------------------------------------------------------------------------------------------------------------------------------------- 2395 403 376 316 291 254 1125 369 355 301 280 240 ----------------------------------------------------------------------------------------------------------------------------------------------------------- 1126 364 352 302 278 234 1125 363 347 302 279 236 1129 365 349 301 278 235 1127 363 351 299 279 239 1127 365 349 298 283 232 1128 364 348 303 299 235 1134 364 353 301 278 232 1127 363 349 308 280 233 1126 370 347 299 277 233 1126 373 343 300 276 232 ----------------------------------------------------------------------------------------------------------------------------------------------------------- 1128 ms 365 ms 349 ms 301 ms 281 ms 234 ms 0 M/s 0 M/s 0 M/s 0 M/s 0 M/s 0 M/s 100 % 308 % 322 % 373 % 401 % 480 % ----------------------------------------------------------------------------------------------------------------------------------------------------------- JCL HashMap: get OpenHashMap ChainedHashMap ChainedHashMap medium ChainedHashMap large ----------------------------------------------------------------------------------------------- 303 285 261 255 223 284 271 244 242 210 ----------------------------------------------------------------------------------------------- 285 271 243 243 207 287 271 244 244 207 286 271 244 243 209 285 271 245 244 209 286 271 246 244 209 285 270 244 243 207 286 270 244 243 207 286 271 245 243 209 285 271 245 243 210 284 272 255 242 208 ----------------------------------------------------------------------------------------------- 285 ms 271 ms 245 ms 243 ms 208 ms 0 M/s 0 M/s 0 M/s 0 M/s 0 M/s 100 % 105 % 116 % 117 % 136 % ----------------------------------------------------------------------------------------------- Mutable HashMap: apply JCL HashMap: apply JCL HashMap: apply OpenHashMap: apply ChainedHashMap: apply ChainedHashMap medium: apply ChainedHashMap large: apply ------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 829 189 187 163 164 158 149 808 176 173 156 149 149 139 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 813 179 182 161 149 149 138 809 177 178 158 149 149 138 808 173 174 157 149 149 137 823 179 177 156 149 149 137 805 174 173 156 149 149 137 808 175 175 156 149 149 137 826 180 179 158 149 149 137 808 175 175 156 149 149 137 807 175 182 155 149 153 137 821 174 174 154 149 150 137 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 813 ms 176 ms 177 ms 157 ms 149 ms 149 ms 137 ms 0 M/s 0 M/s 0 M/s 0 M/s 0 M/s 0 M/s 0 M/s 100 % 460 % 458 % 517 % 543 % 542 % 590 % ------------------------------------------------------------------------------------------------------------------------------------------------------------------------- TreeHashMap: foreach HashMap: foreach JCL HashMap: foreach OpenHashMap: foreach ChainedHashMap: foreach ChainedHashMap medium: foreach ChainedHashMap large: foreach ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 185 565 228 329 167 141 179 176 560 217 317 141 138 167 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 171 549 216 312 137 137 173 191 579 217 314 137 136 167 171 550 218 313 137 137 169 172 549 215 313 137 137 167 173 548 216 313 139 136 167 173 551 216 313 137 137 168 172 549 217 314 137 137 167 173 554 216 313 137 137 168 171 552 217 312 138 137 167 171 546 216 312 138 144 168 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 174 ms 553 ms 216 ms 313 ms 137 ms 137 ms 168 ms 0 M/s 0 M/s 0 M/s 0 M/s 0 M/s 0 M/s 0 M/s 100 % 31 % 80 % 55 % 126 % 126 % 103 % ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- TreeHashMap: elements.foreach HashMap: elements.foreach JCL HashMap: elements.foreach OpenHashMap: elements.foreach ChainedHashMap: elements.foreach ChainedHashMap medium: elements.foreach ChainedHashMap large: elements.foreach ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 344 551 215 274 211 200 218 316 547 215 257 197 196 218 ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 313 506 215 256 197 196 218 316 506 216 260 197 152 171 315 505 216 257 156 153 171 316 509 214 258 153 156 173 315 513 218 259 153 154 172 315 506 215 257 157 152 171 308 506 216 258 151 152 174 309 509 173 256 152 152 173 258 505 174 195 152 153 172 258 507 172 200 152 157 171 ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 302 ms 507 ms 203 ms 246 ms 162 ms 158 ms 177 ms 0 M/s 0 M/s 0 M/s 0 M/s 0 M/s 0 M/s 0 M/s 100 % 59 % 148 % 123 % 186 % 191 % 170 % ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
| Free embeddable forum powered by Nabble | Forum Help |
