You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Stephen Colebourne <sc...@btopenworld.com> on 2003/03/08 18:43:13 UTC
[collections] Faster than HashMap?
I'd had an idea for a way to create a map thats faster to read than a
HashMap...
The idea was to bytecode generate the mapping from the hashcode to the
index:
public int lookupIndex(Object key) {
switch (key.hashCode()) {
case -1682: // hashcode
return 2; // index of Map.Entry
case 86929 // hashcode
return 0; // index of Map.Entry
case 1596969: // hashcode
return 1; // index of Map.Entry
}
return -1;
}
Simple? No hashcode collisions. Should go faster....
Attached are the java files. My initial testing was with a size 3 map, and
that goes about 40% faster. Unfortunately, the bytecode map's performance
degenerates with size. Depending on exact data size 50 entries or more may
be slower, gradually getting slower.
Of course now I realise that the switch statement in bytecode isn't magical
and is just doing a binary search, so was always going to suffer this
problem. What an idiot I am.
If anyone else wants to take a look and see if I've missed something, or has
another bright idea triggered by this then feel free to take a look at the
code. Otherwise, its not worth adding to [collections]. :-((((
Stephen
Re: [collections] Faster than HashMap?
Posted by Stephen Colebourne <sc...@btopenworld.com>.
Trying to attach the files again...
----- Original Message -----
From: "Juozas Baliuka" <ba...@centras.lt>
To: "Jakarta Commons Developers List" <co...@jakarta.apache.org>
Sent: Saturday, March 08, 2003 7:09 PM
Subject: Re: [collections] Faster than HashMap?
>
> No file is attached.
> It will be faster on "small" maps, but method code size is limited, 65535
> bytes or something like this and it needs some workaround.
>
> ----- Original Message -----
> From: "Stephen Colebourne" <sc...@btopenworld.com>
> To: "Jakarta Commons Developers List" <co...@jakarta.apache.org>
> Sent: Saturday, March 08, 2003 7:43 PM
> Subject: [collections] Faster than HashMap?
>
>
> > I'd had an idea for a way to create a map thats faster to read than a
> > HashMap...
> >
> > The idea was to bytecode generate the mapping from the hashcode to the
> > index:
> > public int lookupIndex(Object key) {
> > switch (key.hashCode()) {
> > case -1682: // hashcode
> > return 2; // index of Map.Entry
> > case 86929 // hashcode
> > return 0; // index of Map.Entry
> > case 1596969: // hashcode
> > return 1; // index of Map.Entry
> > }
> > return -1;
> > }
> >
> > Simple? No hashcode collisions. Should go faster....
> >
> > Attached are the java files. My initial testing was with a size 3 map,
and
> > that goes about 40% faster. Unfortunately, the bytecode map's
performance
> > degenerates with size. Depending on exact data size 50 entries or more
may
> > be slower, gradually getting slower.
> >
> > Of course now I realise that the switch statement in bytecode isn't
> magical
> > and is just doing a binary search, so was always going to suffer this
> > problem. What an idiot I am.
> >
> > If anyone else wants to take a look and see if I've missed something, or
> has
> > another bright idea triggered by this then feel free to take a look at
the
> > code. Otherwise, its not worth adding to [collections]. :-((((
> >
> > Stephen
> >
> >
>
>
> --------------------------------------------------------------------------
--
> ----
>
>
> > ---------------------------------------------------------------------
> > To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> > For additional commands, e-mail: commons-dev-help@jakarta.apache.org
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> For additional commands, e-mail: commons-dev-help@jakarta.apache.org
>
Re: [collections] Faster than HashMap?
Posted by Juozas Baliuka <ba...@centras.lt>.
No file is attached.
It will be faster on "small" maps, but method code size is limited, 65535
bytes or something like this and it needs some workaround.
----- Original Message -----
From: "Stephen Colebourne" <sc...@btopenworld.com>
To: "Jakarta Commons Developers List" <co...@jakarta.apache.org>
Sent: Saturday, March 08, 2003 7:43 PM
Subject: [collections] Faster than HashMap?
> I'd had an idea for a way to create a map thats faster to read than a
> HashMap...
>
> The idea was to bytecode generate the mapping from the hashcode to the
> index:
> public int lookupIndex(Object key) {
> switch (key.hashCode()) {
> case -1682: // hashcode
> return 2; // index of Map.Entry
> case 86929 // hashcode
> return 0; // index of Map.Entry
> case 1596969: // hashcode
> return 1; // index of Map.Entry
> }
> return -1;
> }
>
> Simple? No hashcode collisions. Should go faster....
>
> Attached are the java files. My initial testing was with a size 3 map, and
> that goes about 40% faster. Unfortunately, the bytecode map's performance
> degenerates with size. Depending on exact data size 50 entries or more may
> be slower, gradually getting slower.
>
> Of course now I realise that the switch statement in bytecode isn't
magical
> and is just doing a binary search, so was always going to suffer this
> problem. What an idiot I am.
>
> If anyone else wants to take a look and see if I've missed something, or
has
> another bright idea triggered by this then feel free to take a look at the
> code. Otherwise, its not worth adding to [collections]. :-((((
>
> Stephen
>
>
----------------------------------------------------------------------------
----
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> For additional commands, e-mail: commons-dev-help@jakarta.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org