Mercurial > hg4j

annotate src/org/tmatesoft/hg/util/SparseSet.java @ 299:45dc79e545f5

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Recognize flag options (options with no arguments) in command line sample apps
author Artem Tikhomirov <tikhomirov.artem@gmail.com>
date Sat, 17 Sep 2011 13:26:52 +0200
parents 3dd953c65619
children
rev   line source
260
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
1 /*
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
2 * Copyright (c) 2011 TMate Software Ltd
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
3 *
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
4 * This program is free software; you can redistribute it and/or modify
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
5 * it under the terms of the GNU General Public License as published by
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
6 * the Free Software Foundation; version 2 of the License.
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
7 *
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
8 * This program is distributed in the hope that it will be useful,
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
11 * GNU General Public License for more details.
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
12 *
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
13 * For information on how to redistribute this software under
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
14 * the terms of a license other than GNU General Public License
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
15 * contact TMate Software at support@hg4j.com
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
16 */
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
17 package org.tmatesoft.hg.util;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
18
264
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
19 import java.util.Arrays;
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
20
260
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
21 import org.tmatesoft.hg.internal.Experimental;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
22
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
23 /**
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
24 * WORK IN PROGRESS, DO NOT USE
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
25 * Memory-friendly alternative to HashMap-backed Pool. Set where object can be obtained (not only queried for presence)
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
26 *
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
27 * cpython repo, use of HashMap Pool results in ~6 Mb of Map.Entry and Map.Entry[],
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
28 * while use of SparseSet result in 2 Mb.
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
29 *
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
30 * @author Artem Tikhomirov
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
31 * @author TMate Software Ltd.
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
32 */
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
33 @Experimental(reason="Requires tuning to accomodate to collection size. Present state (6-6-6) is too much for a lot of uses")
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
34 public class SparseSet<T> {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
35
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
36 public static void main(String[] args) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
37 SparseSet<String> ss = new SparseSet<String>();
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
38 String one = Integer.toString(156), two = Integer.toString(1024), three = Integer.toString(1123123);
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
39 ss.put(one);
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
40 ss.put(two);
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
41 ss.put(three);
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
42 System.out.println(one == ss.get(one));
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
43 System.out.println(two == ss.get(two));
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
44 System.out.println(three == ss.get(three));
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
45 System.out.println(null == ss.get("one"));
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
46 System.out.println(one == ss.get(Integer.toString(156)));
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
47 System.out.println(two == ss.get(Integer.toString(1024)));
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
48 System.out.println(three == ss.get(Integer.toString(1123123)));
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
49 ss.dump();
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
50 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
51
264
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
52 @SuppressWarnings("unused")
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
53 private static final int MASK_8BIT = 0xFF, MASK_7BIT = 0x7F, MASK_6BIT = 0x3F, MASK_5BIT = 0x1F, MASK_4BIT = 0x0F;
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
54 private static final int I1_SHIFT = 15, I2_SHIFT = 6, I3_SHIFT = 0;
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
55 // 6, 5, 5
265
3dd953c65619 Generous defaults for SparseSet not to fail on big manifests
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 264
diff changeset
56 private static final int I1_MASK = MASK_7BIT, I2_MASK = MASK_4BIT, I3_MASK = MASK_4BIT;
260
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
57
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
58 private final int[] fixups = new int[] {0x1, 0x10, 0xA, 0xD, 0x1F }; // rehash attempts
264
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
59 private final IndexBranch[] level2 = new IndexBranch[I1_MASK + 1];
260
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
60 private int size = 0;
264
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
61
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
62
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
63 //
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
64 int directPut, neighborPut;
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
65 int[] fixupPut1 = new int[fixups.length], fixupPut2 = new int[fixups.length];;
260
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
66
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
67 public void put(T o) {
264
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
68 final int hash = hash(o);
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
69 final int i1 = (hash >>> I1_SHIFT) & I1_MASK, i2 = (hash >>> I2_SHIFT) & I2_MASK, i3 = (hash >>> I3_SHIFT) & I3_MASK;
260
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
70 LeafBranch l3 = leafBranchPut(i1, i2);
264
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
71 int res;
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
72 if ((res = l3.put(i3, o)) != 0) {
260
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
73 size++;
264
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
74 if (res == 1) {
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
75 directPut++;
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
76 } else if (res == 2) {
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
77 neighborPut++;
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
78 }
260
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
79 return;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
80 }
264
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
81 for (int i = 0; i < fixups.length; i++) {
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
82 int fixup = fixups[i];
260
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
83 l3 = leafBranchPut(i1 ^ fixup, i2);
264
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
84 if (l3.putIfEmptyOrSame(i3, o)) {
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
85 size++;
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
86 fixupPut1[i]++;
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
87 return;
260
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
88 }
264
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
89 l3 = leafBranchPut(i1, i2 ^ fixup);
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
90 if (l3.putIfEmptyOrSame(i3, o)) {
260
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
91 size++;
264
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
92 fixupPut2[i]++;
260
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
93 return;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
94 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
95 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
96 throw new IllegalStateException(String.valueOf(o));
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
97 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
98
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
99 @SuppressWarnings("unchecked")
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
100 public T get(T o) {
264
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
101 final int hash = hash(o);
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
102 final int i1 = (hash >>> I1_SHIFT) & I1_MASK, i2 = (hash >>> I2_SHIFT) & I2_MASK, i3 = (hash >>> I3_SHIFT) & I3_MASK;
260
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
103 //
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
104 LeafBranch l3 = leafBranchGet(i1, i2);
264
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
105 if (l3 == null) {
260
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
106 return null;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
107 }
264
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
108 Object c;
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
109 if ((c = l3.get(i3, o)) != null) {
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
110 return c == l3 ? null : (T) c;
260
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
111 }
264
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
112 if ((c = l3.get(i3 ^ 0x1, o)) != null) {
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
113 return c == l3 ? null : (T) c;
260
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
114 }
264
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
115 if ((c = l3.get(i3 ^ 0x2, o)) != null) {
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
116 return c == l3 ? null : (T) c;
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
117 }
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
118 if ((c = l3.get(i3 ^ 0x3, o)) != null) {
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
119 return c == l3 ? null : (T) c;
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
120 }
260
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
121 for (int fixup : fixups) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
122 Object data = leafValueGet(i1 ^ fixup, i2, i3);
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
123 if (data == null) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
124 return null;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
125 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
126 if (o.equals(data)) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
127 return (T)data;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
128 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
129 data = leafValueGet(i1, i2 ^ fixup, i3);
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
130 if (data == null) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
131 return null;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
132 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
133 if (o.equals(data)) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
134 return (T)data;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
135 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
136 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
137 dump();
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
138 throw new IllegalStateException(String.format("[%d,%d,%d] hash: 0x%X, hash2: 0x%X, %s", i1, i2, i3, o.hashCode(), hash, o));
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
139 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
140
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
141 public int size() {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
142 return size;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
143 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
144 private LeafBranch leafBranchPut(int i1, int i2) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
145 IndexBranch l2 = level2[i1];
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
146 if (l2 == null) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
147 level2[i1] = l2 = new IndexBranch();
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
148 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
149 LeafBranch l3 = l2.leafs[i2];
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
150 if (l3 == null) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
151 l2.leafs[i2] = l3 = new LeafBranch();
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
152 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
153 return l3;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
154 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
155
264
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
156 // unlike regular collection clear, keeps all allocated arrays to minimize gc/reallocate costs
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
157 // do force clean, use #drop
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
158 public void clear() {
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
159 for (int i1 = 0; i1 < level2.length; i1++) {
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
160 IndexBranch l2 = level2[i1];
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
161 if (l2 == null) {
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
162 continue;
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
163 }
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
164 for (int i2 = 0; i2 < l2.leafs.length; i2++) {
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
165 LeafBranch l3 = l2.leafs[i2];
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
166 if (l3 == null) {
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
167 continue;
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
168 }
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
169 for (int i3 = 0; i3 < l3.data.length; i3++) {
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
170 l3.data[i3] = null;
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
171 }
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
172 }
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
173 }
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
174 reset();
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
175 }
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
176
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
177 public void drop() {
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
178 reset();
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
179 for (int i1 = 0; i1 < level2.length; level2[i1++] = null);
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
180 }
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
181
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
182 private void reset() {
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
183 size = 0;
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
184 directPut = neighborPut = 0;
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
185 Arrays.fill(fixupPut1, 0);
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
186 Arrays.fill(fixupPut2, 0);
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
187 }
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
188
260
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
189 private LeafBranch leafBranchGet(int i1, int i2) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
190 IndexBranch l2 = level2[i1];
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
191 if (l2 == null) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
192 return null;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
193 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
194 return l2.leafs[i2];
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
195 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
196
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
197 private Object leafValueGet(int i1, int i2, int i3) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
198 IndexBranch l2 = level2[i1];
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
199 if (l2 == null) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
200 return null;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
201 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
202 LeafBranch l3 = l2.leafs[i2];
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
203 if (l3 == null) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
204 return null;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
205 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
206 return l3.data[i3];
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
207 }
264
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
208
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
209 private int hash(Object o) {
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
210 int h = o.hashCode();
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
211 // HashMap.newHash()
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
212 h ^= (h >>> 20) ^ (h >>> 12);
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
213 return h ^ (h >>> 7) ^ (h >>> 4);
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
214 }
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
215
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
216 @Override
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
217 public String toString() {
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
218 return String.format("SparseSet (0x%02X-0x%02X-0x%02X), %d elements. Direct: %d. Resolutions: neighbour: %d, i1: %s. i2: %s", I1_MASK, I2_MASK, I3_MASK, size, directPut, neighborPut, Arrays.toString(fixupPut1), Arrays.toString(fixupPut2));
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
219 }
260
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
220
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
221 public void dump() {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
222 int count = 0;
264
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
223 System.out.println(toString());
260
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
224 for (int i = 0; i < level2.length; i++) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
225 IndexBranch l2 = level2[i];
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
226 if (l2 == null) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
227 continue;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
228 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
229 for (int j = 0; j < l2.leafs.length; j++) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
230 LeafBranch l3 = l2.leafs[j];
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
231 if (l3 == null) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
232 continue;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
233 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
234 for (int k = 0; k < l3.data.length; k++) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
235 Object d = l3.data[k];
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
236 if (d != null) {
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
237 System.out.printf("[%3d,%3d,%3d] %s\n", i,j,k,d);
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
238 count++;
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
239 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
240 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
241 }
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
242 }
264
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
243 System.out.printf("Total: %d elements\n", count);
260
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
244 }
264
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
245
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
246 private static class IndexBranch {
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
247 private final LeafBranch[] leafs = new LeafBranch[64];
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
248 }
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
249
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
250 private static final class LeafBranch {
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
251 public final Object[] data = new Object[64];
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
252
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
253 public int put(int ix, Object d) {
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
254 if (putIfEmptyOrSame(ix, d)) {
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
255 return 1;
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
256 }
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
257 // try neighbour elements
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
258 if (putIfEmptyOrSame(ix ^ 0x1, d) || putIfEmptyOrSame(ix ^ 0x2, d) || putIfEmptyOrSame(ix ^ 0x3, d)) {
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
259 return 2;
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
260 }
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
261 return 0;
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
262 }
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
263
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
264 public boolean putIfEmptyOrSame(int ix, Object d) {
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
265 if (data[ix] == null || data[ix].equals(d)) {
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
266 data[ix] = d;
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
267 return true;
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
268 }
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
269 return false;
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
270 }
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
271
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
272 /**
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
273 * <code>null</code> result indicates further checks make sense
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
274 * @return <code>this</code> if there's no entry at all, <code>null</code> if entry doesn't match, or entry value itself otherwise
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
275 */
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
276 public Object get(int ix, Object o) {
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
277 if (data[ix] == null) {
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
278 return this;
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
279 }
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
280 if (data[ix].equals(o)) {
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
281 return data[ix];
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
282 }
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
283 return null;
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
284 }
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
285 }
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
286
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
287 //
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
288 // 8 bits per level
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
289 // int i1 = (hash >>> 24) & 0xFF, i2 = (hash >>> 16) & 0xFF , i3 = (hash >>> 8) & 0xFF, i4 = hash & 0xFF;
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
290 //
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
291 // 10, 8, 8 and 6 bits
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
292 // final int i1 = (hash >>> 22) & 0x3FF, i2 = (hash >>> 14) & 0xFF , i3 = (hash >>> 6) & 0xFF, i4 = hash & 0x3F;
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
293 //
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
294 // 8, 6, 6, 6, 6
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
295 // 10, 6, 6, 6, 4
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
296 //
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
297 // 6, 5, 5, 5 = 21 bit
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
298 // hash = hash ^ (hash >>> 24); // incorporate upper byte we don't use into lower to value it
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
299 //final int i1 = (hash >>> 18) & 0x3F, i2 = (hash >>> 12) & 0x1F , i3 = (hash >>> 7) & 0x1F, i4 = (hash >>> 2) & 0x1F;
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
300 // 6, 5, 5
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
301 //hash = hash ^ (hash >>> 16);
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
302 //final int i1 = (hash >>> 10) & 0x3F, i2 = (hash >>> 5) & 0x1F , i3 = hash & 0x1F;
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
303 //
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
304 // 6, 6, 6
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
305 //final int i1 = (hash >>> 15) & 0x3F, i2 = (hash >>> 6) & 0x3F , i3 = hash & 0x3F;
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
306 //
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
307 // 8, 5, 5
6bb5e7ed051a Optimize memory usage (reduce number of objects instantiated) when pooling file names and nodeids during manifest parsing
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 260
diff changeset
308
260
61cb6724ff36 Experimental alternative to HashMap in Pool to reduce memory footprint
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
309 }