I am writing an application where memory, and to a lesser extent speed, are vital. I have found from profiling that I spend a great deal of time in Map and Set operations. While I look at ways to call these methods less, I am wondering whether anyone out there has written, or come across, implementations that significantly improve on access time or memory overhead? or at least, that can improve these things given some assumptions?
我正在编写一个应用程序,其中内存以及较小程度的速度至关重要。我从剖析中发现,我花了很多时间在Map和Set操作中。虽然我在考虑减少调用这些方法的方法,但我想知道是否有人在编写或遇到过显着改进访问时间或内存开销的实现?或者至少,在某些假设的情况下,这可以改善这些事情吗?
From looking at the JDK source I can't believe that it can't be made faster or leaner.
从JDK源代码来看,我无法相信它不能更快或更精简。
I am aware of Commons Collections, but I don't believe it has any implementation whose goal is to be faster or leaner. Same for Google Collections.
我知道Commons Collections,但我不相信它有任何实现,其目标是更快或更精简。 Google Collections也是如此。
Update: Should have noted that I do not need thread safety.
更新:应该注意到我不需要线程安全。
17 个解决方案
#1
Normally these methods are pretty quick. There are a couple of things you should check: are your hash codes implemented? Are they sufficiently uniform? Otherwise you'll get rubbish performance.
通常这些方法非常快。您应该检查几件事情:您的哈希码是否已实施?它们是否足够均匀?否则你会得到垃圾表现。
http://trove4j.sourceforge.net/ <-- this is a bit quicker and saves some memory. I saved a few ms on 50,000 updates
http://trove4j.sourceforge.net/ < - 这有点快,节省了一些内存。我在50,000次更新时节省了几毫秒
Are you sure that you're using maps/sets correctly? i.e. not trying to iterate over all the values or something similar. Also, e.g. don't do a contains and then a remove. Just check the remove.
你确定你正确使用地图/套装吗?即不试图迭代所有的值或类似的东西。另外,例如,不要做一个包含然后删除。只需检查删除。
Also check if you're using Double vs double. I noticed a few ms performance improvements on ten's of thousands of checks.
还要检查你是否使用Double vs double。我注意到数以万计的支票上有几个ms的性能提升。
Have you also set up the initial capacity correctly/appropriately?
您是否也正确/适当地设置了初始容量?
#2
#3
Here are the ones I know, in addition to Google and Commons Collections:
除Google和Commons Collections外,以下是我所知道的:
Of course you can always implement your own data structures which are optimized for your use cases. To be able to help better, we would need to know you access patterns and what kind of data you store in the collections.
当然,您始终可以实现自己的数据结构,这些结构针对您的用例进行了优化。为了能够更好地提供帮助,我们需要了解您访问模式以及您在集合中存储的数据类型。
#4
Try improving the performance of your equals and hashCode methods, this could help speed up the standard containers use of your objects.
尝试提高equals和hashCode方法的性能,这有助于加快标准容器对象的使用速度。
#5
You can extend AbstractMap and/or AbstractSet as a starting point. I did this not too long ago to implement a binary trie based map (the key was an integer, and each "level" on the tree was a bit position. left child was 0 and right child was 1). This worked out well for us because the key was EUI-64 identifiers, and for us most of the time the top 5 bytes were going to be the same.
您可以扩展AbstractMap和/或AbstractSet作为起点。我不久前做了这个来实现基于二进制trie的映射(键是一个整数,树上的每个“级别”都是一个位置。左子是0而右子是1)。这对我们来说效果很好,因为密钥是EUI-64标识符,对我们来说大多数时候前5个字节都是相同的。
To implement an AbstractMap, you need to at the very least implement the entrySet() method, to return a set of Map.Entry, each of which is a key/value pair.
要实现AbstractMap,您至少需要实现entrySet()方法,以返回一组Map.Entry,每个Map.Entry都是一个键/值对。
To implement a set, you extend AbstractSet and supply implementations of size() and iterator().
要实现集合,可以扩展AbstractSet并提供size()和iterator()的实现。
That's at the very least, however. You will want to also implement get and put, since the default map is unmodifiable, and the default implementation of get iterates through the entrySet looking for a match.
然而,这至少是这样。您还需要实现get和put,因为默认映射是不可修改的,并且get的默认实现迭代通过entrySet查找匹配项。
#6
You can possibly save a little on memory by:
您可以通过以下方式节省一点内存:
(a) using a stronger, wider hash code, and thus avoiding having to store the keys;
(a)使用更强大,更宽的哈希码,从而避免必须存储密钥;
(b) by allocating yourself from an array, avoiding creating a separate object per hash table entry.
(b)通过从数组中分配自己,避免为每个哈希表条目创建单独的对象。
In case it's useful, here's a no-frills Java implementation of the Numerical Recipies hash table that I've sometimes found useful. You can key directly on a CharSequence (including Strings), or else you must yourself come up with a strong-ish 64-bit hash function for your objects.
如果它有用,这里是一个简单的数值Recipies哈希表的Java实现,我有时发现它很有用。你可以直接键入CharSequence(包括字符串),否则你必须自己为你的对象提出一个强大的64位哈希函数。
Remember, this implementation doesn't store the keys, so if two items have the same hash code (which you'd expect after hashing in the order of 2^32 or a couple of billion items if you have a good hash function), then one item will overwrite the other:
请记住,此实现不存储密钥,因此如果两个项目具有相同的哈希代码(如果您具有良好的哈希函数,则在2 ^ 32的顺序中进行散列后可以预期,或者如果您具有良好的哈希函数,则需要几十亿个项目)然后一个项目将覆盖另一个项目:
public class CompactMap<E> implements Serializable {
static final long serialVersionUID = 1L;
private static final int MAX_HASH_TABLE_SIZE = 1 << 24;
private static final int MAX_HASH_TABLE_SIZE_WITH_FILL_FACTOR = 1 << 20;
private static final long[] byteTable;
private static final long HSTART = 0xBB40E64DA205B064L;
private static final long HMULT = 7664345821815920749L;
static {
byteTable = new long[256];
long h = 0x544B2FBACAAF1684L;
for (int i = 0; i < 256; i++) {
for (int j = 0; j < 31; j++) {
h = (h >>> 7) ^ h;
h = (h << 11) ^ h;
h = (h >>> 10) ^ h;
}
byteTable[i] = h;
}
}
private int maxValues;
private int[] table;
private int[] nextPtrs;
private long[] hashValues;
private E[] elements;
private int nextHashValuePos;
private int hashMask;
private int size;
@SuppressWarnings("unchecked")
public CompactMap(int maxElements) {
int sz = 128;
int desiredTableSize = maxElements;
if (desiredTableSize < MAX_HASH_TABLE_SIZE_WITH_FILL_FACTOR) {
desiredTableSize = desiredTableSize * 4 / 3;
}
desiredTableSize = Math.min(desiredTableSize, MAX_HASH_TABLE_SIZE);
while (sz < desiredTableSize) {
sz <<= 1;
}
this.maxValues = maxElements;
this.table = new int[sz];
this.nextPtrs = new int[maxValues];
this.hashValues = new long[maxValues];
this.elements = (E[]) new Object[sz];
Arrays.fill(table, -1);
this.hashMask = sz-1;
}
public int size() {
return size;
}
public E put(CharSequence key, E val) {
return put(hash(key), val);
}
public E put(long hash, E val) {
int hc = (int) hash & hashMask;
int[] table = this.table;
int k = table[hc];
if (k != -1) {
int lastk;
do {
if (hashValues[k] == hash) {
E old = elements[k];
elements[k] = val;
return old;
}
lastk = k;
k = nextPtrs[k];
} while (k != -1);
k = nextHashValuePos++;
nextPtrs[lastk] = k;
} else {
k = nextHashValuePos++;
table[hc] = k;
}
if (k >= maxValues) {
throw new IllegalStateException("Hash table full (size " + size + ", k " + k);
}
hashValues[k] = hash;
nextPtrs[k] = -1;
elements[k] = val;
size++;
return null;
}
public E get(long hash) {
int hc = (int) hash & hashMask;
int[] table = this.table;
int k = table[hc];
if (k != -1) {
do {
if (hashValues[k] == hash) {
return elements[k];
}
k = nextPtrs[k];
} while (k != -1);
}
return null;
}
public E get(CharSequence hash) {
return get(hash(hash));
}
public static long hash(CharSequence cs) {
if (cs == null) return 1L;
long h = HSTART;
final long hmult = HMULT;
final long[] ht = byteTable;
for (int i = cs.length()-1; i >= 0; i--) {
char ch = cs.charAt(i);
h = (h * hmult) ^ ht[ch & 0xff];
h = (h * hmult) ^ ht[(ch >>> 8) & 0xff];
}
return h;
}
}
#8
There is at least one implementation in commons-collections that is specifically built for speed: Flat3Map it's pretty specific in that it'll be really quick as long as there are no more than 3 elements.
在commons-collections中至少有一个专门为速度而构建的实现:Flat3Map它非常具体,只要不超过3个元素它就会非常快。
I suspect that you may get more milage through following @thaggie's advice add look at the equals/hashcode method times.
我怀疑你可以通过跟随@ thaggie的建议获得更多的milage添加查看equals / hashcode方法的时间。
#9
You said you profiled some classes but have you done any timings to check their speed? I'm not sure how you'd check their memory usage. It seems like it would be nice to have some specific figures at hand when you're comparing different implementations.
你说你描述了一些课程,但你有没有时间检查他们的速度?我不确定你是如何检查他们的内存使用情况的。当您比较不同的实现时,似乎有一些特定的数字会很好。
#10
There are some notes here and links to several alternative data-structure libraries: http://www.leepoint.net/notes-java/data/collections/ds-alternatives.html
这里有一些注释和几个替代数据结构库的链接:http://www.leepoint.net/notes-java/data/collections/ds-alternatives.html
I'll also throw in a strong vote for fastutil. (mentioned in another response, and on that page) It has more different data structures than you can shake a stick at, and versions optimized for primitive types as keys or values. (A drawback is that the jar file is huge, but you can presumably trim it to just what you need)
我也会对fastutil进行强烈投票。 (在另一个响应中提到,并在该页面上)它具有比您可以动摇的更多不同的数据结构,以及针对基本类型作为键或值优化的版本。 (缺点是jar文件很大,但你可以把它修剪成你需要的)
#11
I went through something like this a couple of years ago -- very large Maps and Sets as well as very many of them. The default Java implementations consumed way too much space. In the end I rolled my own, but only after I examined the actual usage patterns that my code required. For example, I had a known large set of objects that were created early on and some Maps were sparse while others were dense. Other structures grew monotonically (no deletes) while in other places it was faster to use a "collection" and do the occasional but harmless extra work of processing duplicate items than it was to spend the time and space on avoiding duplicates. Many of the implementations I used were array-backed and exploited the fact that my hashcodes were sequentially allocated and thus for dense maps a lookup was just an array access.
几年前我经历过类似的事情 - 非常大的地图和集合以及其中很多。默认的Java实现占用了太多空间。最后我推出了自己的,但只是在我检查了我的代码所需的实际使用模式之后。例如,我有一组已知的大型对象,这些对象是早期创建的,有些地图很稀疏而有些地图很密集。其他结构单调增长(没有删除),而在其他地方,使用“集合”更快,处理重复项目的偶尔但无害的额外工作比花费时间和空间避免重复。我使用的许多实现都是由阵列支持的,并且利用了我的哈希码被顺序分配的事实,因此对于密集映射,查找只是一个数组访问。
Take away messages:
带走消息:
- look at your algorithm,
- consider multiple implementations, and
- remember that most of the libraries out there are catering for general purpose use (eg insert and delete, a range of sizes, neither sparse nor dense, etc) so they're going to have overheads that you can probably avoid.
看看你的算法,
考虑多个实现,和
请记住,大多数库都适用于通用目的(例如插入和删除,一系列大小,既不稀疏也不密集等),因此它们可能会有可能避免的开销。
Oh, and write unit tests...
哦,写单元测试......
#12
At times when I have see Map and Set operations are using a high percentage of CPU, it has indicated that I have over used Map and Set and restructuring my data has almost eliminated collections from the top 10% CPU consumer.
有时当我看到Map和Set操作使用高百分比的CPU时,它表明我已经过度使用Map和Set并且重构我的数据几乎消除了来自前10%CPU消费者的集合。
See if you can avoid copies of collections, iterating over collections and any other operation which results in accessing most of the elements of the collection and creating objects.
查看是否可以避免集合的副本,迭代集合以及导致访问集合的大多数元素和创建对象的任何其他操作。
#13
It's probably not so much the Map or Set which causing the problem, but the objects behind them. Depending upon your problem, you might want a more database-type scheme where "objects" are stored as a bunch of bytes rather than Java Objects. You could embed a database (such as Apache Derby) or do your own specialist thing. It's very dependent upon what you are actually doing. HashMap isn't deliberately big and slow...
它可能不是导致问题的Map或Set,而是它们背后的对象。根据您的问题,您可能需要更多数据库类型的方案,其中“对象”存储为一堆字节而不是Java对象。您可以嵌入数据库(例如Apache Derby)或做自己的专家。这非常依赖于你实际在做什么。 HashMap并不是故意大而慢......
#14
Commons Collections has FastArrayList, FastHashMap and FastTreeMap but I don't know what they're worth...
Commons Collections有FastArrayList,FastHashMap和FastTreeMap,但我不知道它们的价值......
#15
- Commons Collections has an id map which compares through ==, which should be faster. -
[Joda Primities][1]as has primitive collections, as does Trove. I experimented with Trove and found that its memory useage is better. - I was mapping collections of many small objects with a few Integers. altering these to ints saved nearly half the memory (although requiring some messier application code to compensate).
- It seems reasonable to me that sorted trees should consume less memory than hashmaps because they don't require the load factor (although if anyone can confirm or has a reason why this is actually dumb please post in the comments).
Commons Collections有一个id映射,通过==进行比较,它应该更快。 - [Joda Primities] [1]和原始集合一样,Trove也是如此。我对Trove进行了实验,发现其内存使用效果更好。
我正在使用一些整数来映射许多小对象的集合。将这些更改为int可以节省近一半的内存(尽管需要一些更复杂的应用程序代码来补偿)。
对我来说,有条理的树应该比hashmaps消耗更少的内存似乎是合理的,因为它们不需要加载因子(尽管如果有人可以确认或有理由为什么这实际上是愚蠢的,请在评论中发布)。
#16
Which version of the JVM are you using?
您使用的是哪个版本的JVM?
If you are not on 6 (although I suspect you are) then a switch to 6 may help.
如果你不在6岁(虽然我怀疑你是),那么切换到6可能有所帮助。
If this is a server application and is running on windows try using -server to use the correct hotspot implementation.
如果这是一个服务器应用程序并在Windows上运行,请尝试使用-server来使用正确的热点实现。
#17
I use the following package (koloboke) to do a int-int hashmap, because it supports promitive type and it stores two int in a long variable, this is cool for me. koloboke
我使用下面的包(koloboke)来做一个int-int hashmap,因为它支持promiable类型,并且它在一个long变量中存储了两个int,这对我来说很酷。 koloboke
#1
Normally these methods are pretty quick. There are a couple of things you should check: are your hash codes implemented? Are they sufficiently uniform? Otherwise you'll get rubbish performance.
通常这些方法非常快。您应该检查几件事情:您的哈希码是否已实施?它们是否足够均匀?否则你会得到垃圾表现。
http://trove4j.sourceforge.net/ <-- this is a bit quicker and saves some memory. I saved a few ms on 50,000 updates
http://trove4j.sourceforge.net/ < - 这有点快,节省了一些内存。我在50,000次更新时节省了几毫秒
Are you sure that you're using maps/sets correctly? i.e. not trying to iterate over all the values or something similar. Also, e.g. don't do a contains and then a remove. Just check the remove.
你确定你正确使用地图/套装吗?即不试图迭代所有的值或类似的东西。另外,例如,不要做一个包含然后删除。只需检查删除。
Also check if you're using Double vs double. I noticed a few ms performance improvements on ten's of thousands of checks.
还要检查你是否使用Double vs double。我注意到数以万计的支票上有几个ms的性能提升。
Have you also set up the initial capacity correctly/appropriately?
您是否也正确/适当地设置了初始容量?
#2
Have you looked at Trove4J ? From the website:
你看过Trove4J吗?来自网站:
Trove aims to provide fast, lightweight implementations of the java.util.Collections API.
Trove旨在提供java.util.Collections API的快速轻量级实现。
Benchmarks provided here.
基准在这里提供。
#3
Here are the ones I know, in addition to Google and Commons Collections:
除Google和Commons Collections外,以下是我所知道的:
Of course you can always implement your own data structures which are optimized for your use cases. To be able to help better, we would need to know you access patterns and what kind of data you store in the collections.
当然,您始终可以实现自己的数据结构,这些结构针对您的用例进行了优化。为了能够更好地提供帮助,我们需要了解您访问模式以及您在集合中存储的数据类型。
#4
Try improving the performance of your equals and hashCode methods, this could help speed up the standard containers use of your objects.
尝试提高equals和hashCode方法的性能,这有助于加快标准容器对象的使用速度。
#5
You can extend AbstractMap and/or AbstractSet as a starting point. I did this not too long ago to implement a binary trie based map (the key was an integer, and each "level" on the tree was a bit position. left child was 0 and right child was 1). This worked out well for us because the key was EUI-64 identifiers, and for us most of the time the top 5 bytes were going to be the same.
您可以扩展AbstractMap和/或AbstractSet作为起点。我不久前做了这个来实现基于二进制trie的映射(键是一个整数,树上的每个“级别”都是一个位置。左子是0而右子是1)。这对我们来说效果很好,因为密钥是EUI-64标识符,对我们来说大多数时候前5个字节都是相同的。
To implement an AbstractMap, you need to at the very least implement the entrySet() method, to return a set of Map.Entry, each of which is a key/value pair.
要实现AbstractMap,您至少需要实现entrySet()方法,以返回一组Map.Entry,每个Map.Entry都是一个键/值对。
To implement a set, you extend AbstractSet and supply implementations of size() and iterator().
要实现集合,可以扩展AbstractSet并提供size()和iterator()的实现。
That's at the very least, however. You will want to also implement get and put, since the default map is unmodifiable, and the default implementation of get iterates through the entrySet looking for a match.
然而,这至少是这样。您还需要实现get和put,因为默认映射是不可修改的,并且get的默认实现迭代通过entrySet查找匹配项。
#6
You can possibly save a little on memory by:
您可以通过以下方式节省一点内存:
(a) using a stronger, wider hash code, and thus avoiding having to store the keys;
(a)使用更强大,更宽的哈希码,从而避免必须存储密钥;
(b) by allocating yourself from an array, avoiding creating a separate object per hash table entry.
(b)通过从数组中分配自己,避免为每个哈希表条目创建单独的对象。
In case it's useful, here's a no-frills Java implementation of the Numerical Recipies hash table that I've sometimes found useful. You can key directly on a CharSequence (including Strings), or else you must yourself come up with a strong-ish 64-bit hash function for your objects.
如果它有用,这里是一个简单的数值Recipies哈希表的Java实现,我有时发现它很有用。你可以直接键入CharSequence(包括字符串),否则你必须自己为你的对象提出一个强大的64位哈希函数。
Remember, this implementation doesn't store the keys, so if two items have the same hash code (which you'd expect after hashing in the order of 2^32 or a couple of billion items if you have a good hash function), then one item will overwrite the other:
请记住,此实现不存储密钥,因此如果两个项目具有相同的哈希代码(如果您具有良好的哈希函数,则在2 ^ 32的顺序中进行散列后可以预期,或者如果您具有良好的哈希函数,则需要几十亿个项目)然后一个项目将覆盖另一个项目:
public class CompactMap<E> implements Serializable {
static final long serialVersionUID = 1L;
private static final int MAX_HASH_TABLE_SIZE = 1 << 24;
private static final int MAX_HASH_TABLE_SIZE_WITH_FILL_FACTOR = 1 << 20;
private static final long[] byteTable;
private static final long HSTART = 0xBB40E64DA205B064L;
private static final long HMULT = 7664345821815920749L;
static {
byteTable = new long[256];
long h = 0x544B2FBACAAF1684L;
for (int i = 0; i < 256; i++) {
for (int j = 0; j < 31; j++) {
h = (h >>> 7) ^ h;
h = (h << 11) ^ h;
h = (h >>> 10) ^ h;
}
byteTable[i] = h;
}
}
private int maxValues;
private int[] table;
private int[] nextPtrs;
private long[] hashValues;
private E[] elements;
private int nextHashValuePos;
private int hashMask;
private int size;
@SuppressWarnings("unchecked")
public CompactMap(int maxElements) {
int sz = 128;
int desiredTableSize = maxElements;
if (desiredTableSize < MAX_HASH_TABLE_SIZE_WITH_FILL_FACTOR) {
desiredTableSize = desiredTableSize * 4 / 3;
}
desiredTableSize = Math.min(desiredTableSize, MAX_HASH_TABLE_SIZE);
while (sz < desiredTableSize) {
sz <<= 1;
}
this.maxValues = maxElements;
this.table = new int[sz];
this.nextPtrs = new int[maxValues];
this.hashValues = new long[maxValues];
this.elements = (E[]) new Object[sz];
Arrays.fill(table, -1);
this.hashMask = sz-1;
}
public int size() {
return size;
}
public E put(CharSequence key, E val) {
return put(hash(key), val);
}
public E put(long hash, E val) {
int hc = (int) hash & hashMask;
int[] table = this.table;
int k = table[hc];
if (k != -1) {
int lastk;
do {
if (hashValues[k] == hash) {
E old = elements[k];
elements[k] = val;
return old;
}
lastk = k;
k = nextPtrs[k];
} while (k != -1);
k = nextHashValuePos++;
nextPtrs[lastk] = k;
} else {
k = nextHashValuePos++;
table[hc] = k;
}
if (k >= maxValues) {
throw new IllegalStateException("Hash table full (size " + size + ", k " + k);
}
hashValues[k] = hash;
nextPtrs[k] = -1;
elements[k] = val;
size++;
return null;
}
public E get(long hash) {
int hc = (int) hash & hashMask;
int[] table = this.table;
int k = table[hc];
if (k != -1) {
do {
if (hashValues[k] == hash) {
return elements[k];
}
k = nextPtrs[k];
} while (k != -1);
}
return null;
}
public E get(CharSequence hash) {
return get(hash(hash));
}
public static long hash(CharSequence cs) {
if (cs == null) return 1L;
long h = HSTART;
final long hmult = HMULT;
final long[] ht = byteTable;
for (int i = cs.length()-1; i >= 0; i--) {
char ch = cs.charAt(i);
h = (h * hmult) ^ ht[ch & 0xff];
h = (h * hmult) ^ ht[(ch >>> 8) & 0xff];
}
return h;
}
}
#7
#8
There is at least one implementation in commons-collections that is specifically built for speed: Flat3Map it's pretty specific in that it'll be really quick as long as there are no more than 3 elements.
在commons-collections中至少有一个专门为速度而构建的实现:Flat3Map它非常具体,只要不超过3个元素它就会非常快。
I suspect that you may get more milage through following @thaggie's advice add look at the equals/hashcode method times.
我怀疑你可以通过跟随@ thaggie的建议获得更多的milage添加查看equals / hashcode方法的时间。
#9
You said you profiled some classes but have you done any timings to check their speed? I'm not sure how you'd check their memory usage. It seems like it would be nice to have some specific figures at hand when you're comparing different implementations.
你说你描述了一些课程,但你有没有时间检查他们的速度?我不确定你是如何检查他们的内存使用情况的。当您比较不同的实现时,似乎有一些特定的数字会很好。
#10
There are some notes here and links to several alternative data-structure libraries: http://www.leepoint.net/notes-java/data/collections/ds-alternatives.html
这里有一些注释和几个替代数据结构库的链接:http://www.leepoint.net/notes-java/data/collections/ds-alternatives.html
I'll also throw in a strong vote for fastutil. (mentioned in another response, and on that page) It has more different data structures than you can shake a stick at, and versions optimized for primitive types as keys or values. (A drawback is that the jar file is huge, but you can presumably trim it to just what you need)
我也会对fastutil进行强烈投票。 (在另一个响应中提到,并在该页面上)它具有比您可以动摇的更多不同的数据结构,以及针对基本类型作为键或值优化的版本。 (缺点是jar文件很大,但你可以把它修剪成你需要的)
#11
I went through something like this a couple of years ago -- very large Maps and Sets as well as very many of them. The default Java implementations consumed way too much space. In the end I rolled my own, but only after I examined the actual usage patterns that my code required. For example, I had a known large set of objects that were created early on and some Maps were sparse while others were dense. Other structures grew monotonically (no deletes) while in other places it was faster to use a "collection" and do the occasional but harmless extra work of processing duplicate items than it was to spend the time and space on avoiding duplicates. Many of the implementations I used were array-backed and exploited the fact that my hashcodes were sequentially allocated and thus for dense maps a lookup was just an array access.
几年前我经历过类似的事情 - 非常大的地图和集合以及其中很多。默认的Java实现占用了太多空间。最后我推出了自己的,但只是在我检查了我的代码所需的实际使用模式之后。例如,我有一组已知的大型对象,这些对象是早期创建的,有些地图很稀疏而有些地图很密集。其他结构单调增长(没有删除),而在其他地方,使用“集合”更快,处理重复项目的偶尔但无害的额外工作比花费时间和空间避免重复。我使用的许多实现都是由阵列支持的,并且利用了我的哈希码被顺序分配的事实,因此对于密集映射,查找只是一个数组访问。
Take away messages:
带走消息:
- look at your algorithm,
- consider multiple implementations, and
- remember that most of the libraries out there are catering for general purpose use (eg insert and delete, a range of sizes, neither sparse nor dense, etc) so they're going to have overheads that you can probably avoid.
看看你的算法,
考虑多个实现,和
请记住,大多数库都适用于通用目的(例如插入和删除,一系列大小,既不稀疏也不密集等),因此它们可能会有可能避免的开销。
Oh, and write unit tests...
哦,写单元测试......
#12
At times when I have see Map and Set operations are using a high percentage of CPU, it has indicated that I have over used Map and Set and restructuring my data has almost eliminated collections from the top 10% CPU consumer.
有时当我看到Map和Set操作使用高百分比的CPU时,它表明我已经过度使用Map和Set并且重构我的数据几乎消除了来自前10%CPU消费者的集合。
See if you can avoid copies of collections, iterating over collections and any other operation which results in accessing most of the elements of the collection and creating objects.
查看是否可以避免集合的副本,迭代集合以及导致访问集合的大多数元素和创建对象的任何其他操作。
#13
It's probably not so much the Map or Set which causing the problem, but the objects behind them. Depending upon your problem, you might want a more database-type scheme where "objects" are stored as a bunch of bytes rather than Java Objects. You could embed a database (such as Apache Derby) or do your own specialist thing. It's very dependent upon what you are actually doing. HashMap isn't deliberately big and slow...
它可能不是导致问题的Map或Set,而是它们背后的对象。根据您的问题,您可能需要更多数据库类型的方案,其中“对象”存储为一堆字节而不是Java对象。您可以嵌入数据库(例如Apache Derby)或做自己的专家。这非常依赖于你实际在做什么。 HashMap并不是故意大而慢......
#14
Commons Collections has FastArrayList, FastHashMap and FastTreeMap but I don't know what they're worth...
Commons Collections有FastArrayList,FastHashMap和FastTreeMap,但我不知道它们的价值......
#15
- Commons Collections has an id map which compares through ==, which should be faster. -
[Joda Primities][1]as has primitive collections, as does Trove. I experimented with Trove and found that its memory useage is better. - I was mapping collections of many small objects with a few Integers. altering these to ints saved nearly half the memory (although requiring some messier application code to compensate).
- It seems reasonable to me that sorted trees should consume less memory than hashmaps because they don't require the load factor (although if anyone can confirm or has a reason why this is actually dumb please post in the comments).
Commons Collections有一个id映射,通过==进行比较,它应该更快。 - [Joda Primities] [1]和原始集合一样,Trove也是如此。我对Trove进行了实验,发现其内存使用效果更好。
我正在使用一些整数来映射许多小对象的集合。将这些更改为int可以节省近一半的内存(尽管需要一些更复杂的应用程序代码来补偿)。
对我来说,有条理的树应该比hashmaps消耗更少的内存似乎是合理的,因为它们不需要加载因子(尽管如果有人可以确认或有理由为什么这实际上是愚蠢的,请在评论中发布)。
#16
Which version of the JVM are you using?
您使用的是哪个版本的JVM?
If you are not on 6 (although I suspect you are) then a switch to 6 may help.
如果你不在6岁(虽然我怀疑你是),那么切换到6可能有所帮助。
If this is a server application and is running on windows try using -server to use the correct hotspot implementation.
如果这是一个服务器应用程序并在Windows上运行,请尝试使用-server来使用正确的热点实现。
#17
I use the following package (koloboke) to do a int-int hashmap, because it supports promitive type and it stores two int in a long variable, this is cool for me. koloboke
我使用下面的包(koloboke)来做一个int-int hashmap,因为它支持promiable类型,并且它在一个long变量中存储了两个int,这对我来说很酷。 koloboke