Mercurial > jhg

comparison src/org/tmatesoft/hg/util/SparseSet.java @ 260:61cb6724ff36

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Experimental alternative to HashMap in Pool to reduce memory footprint
author Artem Tikhomirov <tikhomirov.artem@gmail.com>
date Wed, 17 Aug 2011 02:35:15 +0200
parents
children 6bb5e7ed051a
comparison
equal deleted inserted replaced
259:ea0c0de86d0e 260:61cb6724ff36
1 /*
2 * Copyright (c) 2011 TMate Software Ltd
3 *
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; version 2 of the License.
7 *
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 * GNU General Public License for more details.
12 *
13 * For information on how to redistribute this software under
14 * the terms of a license other than GNU General Public License
15 * contact TMate Software at support@hg4j.com
16 */
17 package org.tmatesoft.hg.util;
18
19 import org.tmatesoft.hg.internal.Experimental;
20
21 /**
22 * WORK IN PROGRESS, DO NOT USE
23 * Memory-friendly alternative to HashMap-backed Pool. Set where object can be obtained (not only queried for presence)
24 *
25 * cpython repo, use of HashMap Pool results in ~6 Mb of Map.Entry and Map.Entry[],
26 * while use of SparseSet result in 2 Mb.
27 *
28 * @author Artem Tikhomirov
29 * @author TMate Software Ltd.
30 */
31 @Experimental(reason="Requires tuning to accomodate to collection size. Present state (6-6-6) is too much for a lot of uses")
32 public class SparseSet<T> {
33
34 public static void main(String[] args) {
35 SparseSet<String> ss = new SparseSet<String>();
36 String one = Integer.toString(156), two = Integer.toString(1024), three = Integer.toString(1123123);
37 ss.put(one);
38 ss.put(two);
39 ss.put(three);
40 System.out.println(one == ss.get(one));
41 System.out.println(two == ss.get(two));
42 System.out.println(three == ss.get(three));
43 System.out.println(null == ss.get("one"));
44 System.out.println(one == ss.get(Integer.toString(156)));
45 System.out.println(two == ss.get(Integer.toString(1024)));
46 System.out.println(three == ss.get(Integer.toString(1123123)));
47 ss.dump();
48 }
49
50 private static class IndexBranch {
51 private final LeafBranch[] leafs = new LeafBranch[64];
52 }
53 private static class LeafBranch {
54 private final Object[] data = new Object[64];
55 }
56
57 private final int[] fixups = new int[] {0x1, 0x10, 0xA, 0xD, 0x1F }; // rehash attempts
58 private final IndexBranch[] level2 = new IndexBranch[64];
59 private int size = 0;
60
61 public void put(T o) {
62 int hash = o.hashCode();
63 //
64 // 8 bits per level
65 // int i1 = (hash >>> 24) & 0xFF, i2 = (hash >>> 16) & 0xFF , i3 = (hash >>> 8) & 0xFF, i4 = hash & 0xFF;
66 //
67 // 10, 8, 8 and 6 bits
68 // final int i1 = (hash >>> 22) & 0x3FF, i2 = (hash >>> 14) & 0xFF , i3 = (hash >>> 6) & 0xFF, i4 = hash & 0x3F;
69 //
70 // 8, 6, 6, 6, 6
71 // 10, 6, 6, 6, 4
72 //
73 // 6, 5, 5, 5 = 21 bit
74 // hash = hash ^ (hash >>> 24); // incorporate upper byte we don't use into lower to value it
75 // final int i1 = (hash >>> 18) & 0x3F, i2 = (hash >>> 12) & 0x1F , i3 = (hash >>> 7) & 0x1F, i4 = (hash >>> 2) & 0x1F;
76 // 6, 5, 5
77 // hash = hash ^ (hash >>> 16);
78 // final int i1 = (hash >>> 10) & 0x3F, i2 = (hash >>> 5) & 0x1F , i3 = hash & 0x1F;
79 //
80 // 6, 6, 6
81 final int i1 = (hash >>> 15) & 0x3F, i2 = (hash >>> 6) & 0x3F , i3 = hash & 0x3F;
82 LeafBranch l3 = leafBranchPut(i1, i2);
83 if (l3.data[i3] == null) {
84 l3.data[i3] = o;
85 size++;
86 return;
87 }
88 int neighbour = (i3+1) & 0x3F;
89 if (l3.data[neighbour] == null) {
90 l3.data[neighbour] = o;
91 size++;
92 return;
93 }
94 int conflictCount = 0;
95 for (int fixup : fixups) {
96 // if (showConflicts) {
97 // System.out.printf("(fixup: 0x%x) ", fixup);
98 // }
99 l3 = leafBranchPut(i1 ^ fixup, i2);
100 conflictCount++;
101 if (l3.data[i3] != null) {
102 // if (showConflicts) {
103 // System.out.printf("i1 failed ");
104 // }
105 l3 = leafBranchPut(i1, i2 ^ fixup);
106 conflictCount++;
107 // if (showConflicts) {
108 // System.out.printf("i2 %s ", (l3.data[i3] == null) ? "ok" : "failed");
109 // }
110 // } else {
111 // if (showConflicts) {
112 // System.out.printf("i1 ok");
113 // }
114 }
115 // if (showConflicts) {
116 // System.out.println();
117 // }
118 if (l3.data[i3] == null) {
119 l3.data[i3] = o;
120 // System.out.printf("Resolved conflict in %d steps (fixup 0x%X)\n", conflictCount, fixup);
121 size++;
122 return;
123 }
124 }
125 throw new IllegalStateException(String.valueOf(o));
126 }
127
128 @SuppressWarnings("unchecked")
129 public T get(T o) {
130 int hash = o.hashCode();
131 //hash = hash ^ (hash >>> 16);
132 final int i1 = (hash >>> 15) & 0x3F, i2 = (hash >>> 6) & 0x3F , i3 = hash & 0x3F;
133 //
134 LeafBranch l3 = leafBranchGet(i1, i2);
135 if (l3 == null || l3.data[i3] == null) {
136 return null;
137 }
138 if (o.equals(l3.data[i3])) {
139 return (T) l3.data[i3];
140 }
141 //
142 int neighbour = (i3+1) & 0x3F;
143 if (o.equals(l3.data[neighbour])) {
144 return (T) l3.data[neighbour];
145 }
146
147 //
148 // resolve conflict
149 for (int fixup : fixups) {
150 Object data = leafValueGet(i1 ^ fixup, i2, i3);
151 if (data == null) {
152 return null;
153 }
154 if (o.equals(data)) {
155 return (T)data;
156 }
157 data = leafValueGet(i1, i2 ^ fixup, i3);
158 if (data == null) {
159 return null;
160 }
161 if (o.equals(data)) {
162 return (T)data;
163 }
164 }
165 dump();
166 throw new IllegalStateException(String.format("[%d,%d,%d] hash: 0x%X, hash2: 0x%X, %s", i1, i2, i3, o.hashCode(), hash, o));
167 }
168
169 public int size() {
170 return size;
171 }
172 private LeafBranch leafBranchPut(int i1, int i2) {
173 IndexBranch l2 = level2[i1];
174 if (l2 == null) {
175 level2[i1] = l2 = new IndexBranch();
176 }
177 LeafBranch l3 = l2.leafs[i2];
178 if (l3 == null) {
179 l2.leafs[i2] = l3 = new LeafBranch();
180 }
181 return l3;
182 }
183
184 private LeafBranch leafBranchGet(int i1, int i2) {
185 IndexBranch l2 = level2[i1];
186 if (l2 == null) {
187 return null;
188 }
189 return l2.leafs[i2];
190 }
191
192 private Object leafValueGet(int i1, int i2, int i3) {
193 IndexBranch l2 = level2[i1];
194 if (l2 == null) {
195 return null;
196 }
197 LeafBranch l3 = l2.leafs[i2];
198 if (l3 == null) {
199 return null;
200 }
201 return l3.data[i3];
202 }
203
204 public void dump() {
205 int count = 0;
206 for (int i = 0; i < level2.length; i++) {
207 IndexBranch l2 = level2[i];
208 if (l2 == null) {
209 continue;
210 }
211 for (int j = 0; j < l2.leafs.length; j++) {
212 LeafBranch l3 = l2.leafs[j];
213 if (l3 == null) {
214 continue;
215 }
216 for (int k = 0; k < l3.data.length; k++) {
217 Object d = l3.data[k];
218 if (d != null) {
219 System.out.printf("[%3d,%3d,%3d] %s\n", i,j,k,d);
220 count++;
221 }
222 }
223 }
224 }
225 System.out.printf("Total: %d elements", count);
226 }
227 }