Doug,
On Wed, Jul 22, 2009 at 8:21 PM, Doug Lead...@cs.oswego.edu wrote:
On further evaluating it (among other possible HashMap replacements),
I'm not convinced that they are enough better to commit.
Size:... 9216 36864 147456 589824
HashMap ...45 97208273
V2
somehow 10
days
for you is the same as 2 days for the rest of us. :)
(Well, I was unexpectedly stranded at JFK for 20 hrs, but
now really am in sporadic e-mail mode for 9 days.)
More seriously, it would be great to have a HashMap that takes less memory
and
performs as well or better so I
Doug Lea a écrit :
somehow 10
days
for you is the same as 2 days for the rest of us. :)
(Well, I was unexpectedly stranded at JFK for 20 hrs, but
now really am in sporadic e-mail mode for 9 days.)
More seriously, it would be great to have a HashMap that takes less memory
and
Hi Doug,
In a previous message you said:
There are a few remaining things to consider
before taking this too seriously as a replacement.
I'll be out for 10 days starting tomorrow so probably
won't get a chance to do so soon.
I now understand the secret behind your productivity levels... somehow
While I'm posting in-progress stuff, here are some other notes on hash
maps:
First, some observations about usage (repeating some
already posted):
Via some dated but probably still valid dynamic measurments:
Ops: Approx 84% read, 15% add/modify, 1% remove
Sizes: Peak at 0, 1, 2, then
Inspired by the combination of Alex's efforts and ongoing
work on concurrent caches, I put together a version
of HashMap (called HashMapV2 for now) with a snapshot at
http://gee.cs.oswego.edu/dl/wwwtmp/HashMapV2.java
(This retains the openjdk GPL header etc.)
There are a few remaining things
Also it should be mentioned that memory-wise my implementation
uses more memory in resize: it need to copy 2 arrays of ~2*C size
(C = capacity) and current HashMap needs only one array of C size,
data in Entry structures are not copied. This can be addressed
if it is important by (1) splitting
Doug,
On Tue, Jun 9, 2009 at 4:09 PM, Doug Lea d...@cs.oswego.edu wrote:
Alex Yakovlev wrote:
entrySet() iterator which is very expensive.
Very big speedup would be to reuse Entry object,
We had originally done this in a few classes.
The Iterator spec even allows it. However, most
Alex Yakovlev wrote:
Doug,
I've finished HashMap, HashSet, LinkedHashMap, and LinkedHashSet
porting to my approach. I run several tests I've found in
jdk/test/java/util/*
that are directly related to these classes, not sure I've found all of them.
There are a lot of tests around for
A few notes on your implementation...
Alex Yakovlev wrote:
Main trick is in storing all data in 2 arrays without any HashEntry objects.
One is array of Objects with keys and values, another in a complex array
of indices.
Notice that footprint comparisons with current HashMap
are
* Doug Lea:
I once instrumented some of the reference workload usages
and found that over half of the HashMaps/Hashtables had
a max 3 or fewer elements during their lifetimes.
So on average using your version will likely increase
application footprints. It seems possible to deal with
this
2009/6/8 Doug Lea d...@cs.oswego.edu:
It is possible to use a look-aside strategy for tiny
HashMaps. I think one of the Apache commons maps
does this.
FYI - Commons Collections Flat3Map:
http://commons.apache.org/collections/api-3.2/org/apache/commons/collections/map/Flat3Map.html
Stephen
Doug,
I've finished HashMap, HashSet, LinkedHashMap, and LinkedHashSet
porting to my approach. I run several tests I've found in
jdk/test/java/util/*
that are directly related to these classes, not sure I've found all of them.
I have not compiled the whole jdk classes - only these 4 (removed
Alex,
Might I suggest you look at the test framework in Google
Collectionshttp://code.google.com/p/google-collections/?
Extremely good coverage and only a couple of lines to set up.
Tests for maps in java.util:
Joe,
Thank you for the link.
What I found strange is that non-Linked versions
(simple HashSet and HashMap)
passes all tests with CollectionFeature.KNOWN_ORDER
TestSuite source I ran (scala):
http://github.com/alex14n/CompactHashMap/blob/e2b81fb9ccf5446eff961d86eb3a0dc084a8a88c/test/Tests.scala
Doug,
On Thu, Jun 4, 2009 at 4:32 PM, Doug Lea d...@cs.oswego.edu wrote:
The main one is that LinkedHashMap is declared as a
subclass of HashMap. There's not
an obvious way to add insertion- or access- ordered links
to your version.
Well, it can be done by adding another index array,
I've
Hello,
While playing with scala programming language I've come to a HashMap
implementation
that appears to be faster than current java.util.HashMap, also with a lower
memory footprint.
Alex Miller advised me to post about it in this maillist.
I've put current implementation (both scala and
17 matches
Mail list logo
