All, On 12/29/11 3:25 PM, Christopher Schultz wrote: > On 12/29/11 12:35 PM, Luke Meyer wrote: >> Worth noting that TreeMap makes all storage O(log n), so the normal >> case takes a hit in order to mitigate the worst case (i.e. malicious >> case). > > When n is small, though, O(n) ~= O(log n). > > I'd be interested to see the relative performance of each of these > implementations. A straightforward test can be performed to test raw > speed, but the memory-versus-protection issue is really a subjective one.
I have some performance numbers along with the code below. It looks like
the performance trade-off for a TreeMap becomes viable around 10000
elements. Coincidentally, that's about the same time that the hashtable
collision becomes a vulnerability.
We could have HttpSession switch from using a HashMap to a TreeMap when
the size hits 10000 elements, and even make that an option on the <Context>.
Here are 3 runs, all single-threaded on this machine (though virtualized):
model name : Intel(R) Xeon(R) CPU E5430 @ 2.66GHz
stepping : 10
cpu MHz : 2666.758
cache size : 6144 KB
> $ java -server -showversion HashCollissionTest
> java version "1.6.0_26"
> Java(TM) SE Runtime Environment (build 1.6.0_26-b03)
> Java HotSpot(TM) 64-Bit Server VM (build 20.1-b02, mixed mode)
>
> Initializing strings...
> Done
> Running tests...
> Regular Strings Colliding Strings
> | HashMap TreeMap Speedup HashMap TreeMap Speedup
> 10 | 44989ns 315370ns 0.1x 63690ns 67143ns 0.9x
> 10 | 16196ns 40469ns 0.4x 28379ns 37904ns 0.7x
> 100 | 86546ns 460331ns 0.2x 790022ns 444854ns 1.8x
> 100 | 87558ns 465158ns 0.2x 769854ns 422202ns 1.8x
> 1000 | 442763ns 18439396ns 0.0x 3079022ns 5555242ns 0.6x
> 1000 | 317509ns 15997482ns 0.0x 20380195ns 14069753ns 1.4x
> 10000 | 13289497ns 3096187ns 4.3x 336093160ns 3080478ns 109.1x
> 10000 | 700149ns 19021731ns 0.0x 348387091ns 3070681ns 113.5x
> 100000 | 22356925ns 58920791ns 0.4x 40533164686ns 63963787ns 633.7x
> 100000 | 9270803ns 49062417ns 0.2x 40312204850ns 51424106ns 783.9x
>
>
> Initializing strings...
> Done
> Running tests...
> Regular Strings Colliding Strings
> | HashMap TreeMap Speedup HashMap TreeMap Speedup
> 10 | 46390ns 315255ns 0.1x 60600ns 67837ns 0.9x
> 10 | 15968ns 40223ns 0.4x 25688ns 37451ns 0.7x
> 100 | 105515ns 447747ns 0.2x 779985ns 452651ns 1.7x
> 100 | 93377ns 450803ns 0.2x 791133ns 456755ns 1.7x
> 1000 | 902098ns 14199242ns 0.1x 2515629ns 5648127ns 0.4x
> 1000 | 388018ns 5921296ns 0.1x 2525295ns 6146751ns 0.4x
> 10000 | 17576565ns 4645257ns 3.8x 302281637ns 3338971ns 90.5x
> 10000 | 695921ns 2903437ns 0.2x 294269766ns 3032316ns 97.0x
> 100000 | 17441705ns 39965677ns 0.4x 31082207714ns 61067533ns 509.0x
> 100000 | 20723029ns 38217266ns 0.5x 31028693562ns 62811819ns 494.0x
>
>
> Initializing strings...
> Done
> Running tests...
> Regular Strings Colliding Strings
> | HashMap TreeMap Speedup HashMap TreeMap Speedup
> 10 | 45661ns 322867ns 0.1x 74707ns 68256ns 1.1x
> 10 | 14978ns 40684ns 0.4x 25526ns 39590ns 0.6x
> 100 | 101775ns 465944ns 0.2x 804610ns 449270ns 1.8x
> 100 | 89553ns 469063ns 0.2x 937187ns 438083ns 2.1x
> 1000 | 492615ns 8732361ns 0.1x 2530423ns 5512348ns 0.5x
> 1000 | 312919ns 5770171ns 0.1x 2585771ns 5942987ns 0.4x
> 10000 | 10493163ns 15081198ns 0.7x 292524677ns 6026717ns 48.5x
> 10000 | 692544ns 2697905ns 0.3x 306244958ns 2736476ns 111.9x
> 100000 | 10415660ns 55898980ns 0.2x 34549577192ns 56967692ns 606.5x
> 100000 | 17369651ns 46201996ns 0.4x 34596484935ns 56857149ns 608.5x
Here is the code for the above test:
import java.util.Map;
import java.util.HashMap;
import java.util.TreeMap;
public class HashCollissionTest
{
public static void main(String[] args)
{
// Prime the JIT
System.out.println("Running tests...");
System.out.println(" Regular Strings
Colliding Strings");
System.out.println(String.format("%8s | %11s %11s %8s %11s %11s
%8s", "", "HashMap", "TreeMap", "Speedup", "HashMap", "TreeMap",
"Speedup"));
test(10);
test(10);
test(100);
test(100);
test(1000);
test(1000);
test(10000);
test(10000);
test(100000);
test(100000);
}
static void test(int iterations)
{
HashMap<Object,Boolean> hashMap = new HashMap<Object,Boolean>();
TreeMap<Object,Boolean> treeMap = new TreeMap<Object,Boolean>();
long elapsed_hs = System.nanoTime();
test(hashMap, iterations, strings);
elapsed_hs = System.nanoTime() - elapsed_hs;
hashMap.clear();
hashMap = null;
System.gc();
long elapsed_ts = System.nanoTime();
test(treeMap, iterations, strings);
elapsed_ts = System.nanoTime() - elapsed_ts;
treeMap.clear();
treeMap = null;
System.gc();
hashMap = new HashMap<Object,Boolean>();
long elapsed_hss = System.nanoTime();
test(hashMap, iterations, stupidStrings);
elapsed_hss = System.nanoTime() - elapsed_hss;
hashMap.clear();
hashMap = null;
System.gc();
treeMap = new TreeMap<Object,Boolean>();
long elapsed_tss = System.nanoTime();
test(treeMap, iterations, stupidStrings);
elapsed_tss = System.nanoTime() - elapsed_tss;
double p_s = (double)elapsed_hs / (double)elapsed_ts;
double p_ss = (double)elapsed_hss / (double)elapsed_tss;
System.out.println(String.format("%8d | %9dns %9dns % 7.1fx %9dns
%9dns % 7.1fx", iterations, elapsed_hs, elapsed_ts, p_s, elapsed_hss,
elapsed_tss, p_ss));
treeMap.clear();
treeMap = null;
System.gc();
}
static class StupidString
implements Comparable
{
private String _s;
public StupidString(String s)
{
_s = s;
}
public int hashCode() { return 0; }
public String toString() { return _s; }
public boolean equals(Object o) { return _s.equals(o); }
public int compareTo(Object o) { return
_s.compareTo(((StupidString)o)._s); }
}
static void test(Map<Object,Boolean> map, int iterations, Object[] keys)
{
if(iterations > MAX_ITERATIONS)
throw new IllegalArgumentException("Requested " + iterations + "
while " + MAX_ITERATIONS + " is the limit");
for(int i=0; i<iterations; ++i)
map.put(keys[i], Boolean.FALSE);
}
static final int MAX_ITERATIONS = 999999;
static String[] strings;
static StupidString[] stupidStrings;
static
{
System.out.println("Initializing strings...");
stupidStrings = new StupidString[MAX_ITERATIONS];
strings = new String[MAX_ITERATIONS];
for(int i=0; i < MAX_ITERATIONS; ++i)
stupidStrings[i] = new StupidString(strings[i] = String.valueOf(i));
System.out.println("Done");
}
}
-chris
signature.asc
Description: OpenPGP digital signature
