Collections Library for millions of elements

When to use this library


If you want to efficiently store large collections of data in memory. This library can dramatically reduce Full GC times and reduce memory consumption as well.

When you have a data type which can be represented by an interface and you want a List for this type.

List<Iinterfacetype> list = new HugeArrayBuilder<Interfacetype>() {}.create();

The type needs to be described using an interface so its represented can be changed. (Using generated byte code)

The HugeArrayBuilder builds generated classes for the InterfaceType on demand. The builder can be configured to change how the HugeArrayList is created.

A more complex example is
HugeArrayList<Mutabletypes> hugeList = new HugeArrayBuilder<Mutabletypes>() {{
        allocationSize = 1024*1024;
        classLoader = myClassLoader;
    }}.create();

How does the library differ

  • Uses long for sizes and indecies.
  • Uses column based data making the per element overhead minimal and speed up scans over a single or small set of attributes. This reduces memory usages by 2x or more.
  • Stores attributes in direct memory as much as possible, reducing heap usage dramatically, 10x or more.
  • Allocates blocks of data for consistent add() times, rather than exponentially growing an underlying store (with exponentially increasing delays on a grow of capacity)

Performance comparison

This test compares using HugeCollection vs ArrayList of JavaBeans. The class has 12 fields of various types which can be converted to primitives in different ways. By storing these primitives (or objects encoded as primitives), the time to perform GCs is almost eliminated.


With 20 GB of free memory, only 250 million JavaBeans could be created and a HugeCollection can store 500 million elements.

Classes with fields which cannot be encoded as primitives are supported in version 0.1.1 and still show an improvement in GC times.




In both cases, the amount of memory used was halved.

The project web site

HugeCollections on Google Code

The source

The best way to get the whole source, including tests is to use subversion.
svn co http://vanilla-java.googlecode.com/svn/trunk/collections/ vanilla-java-collections
cd vanilla-java-collections
mvn test

Comments

  1. ido14 August 2011 at 08:48

    This sounds great. How is access time and how is append time compared to ArrayList? How does it compare in access time to an Array of the same size?

    ReplyDelete
  2. Peter Lawrey15 August 2011 at 12:23

    @Ido, The write time is higher but the read times lower. If you do a write and a read, the totla time is about 10% higher than for an ArrayList or an Array.

    ReplyDelete
  3. Parwinder Sekhon16 August 2011 at 20:55

    Have you seen http://ehcache.org/documentation/user-guide/bigmemory

    ReplyDelete
  4. Peter Lawrey17 August 2011 at 11:07

    @Parwinder, The difference is that BigMemory uses Serialization/Deserialization. This means you can use polymorphism and regular data value objects. The typical access time for 8 GB is 200 us.

    My approach avoids the need for any serialization which makes the amount of CPU and memory used much lower. Also no garbage is produced. Typical access time is around 0.5 us to perform a update (read+write) a random object!

    You can iterate and update billions of entries without creating significant garbage. ;) (I have a unit test which does exactly that, it creates one Iterator) If you use indexed access, you can avoid any object creation.

    ReplyDelete
  5. Peter Lawrey17 August 2011 at 11:19

    Another difference is that objects in HugeCollections can occupy less memory, typically about half. The overhead of serialization means the objects in BigMemory can be 4x larger for a typical object. Memory is cheap, however cache is limited and more compact data structures can improve performance.

    ReplyDelete
  6. Peter Lawrey17 August 2011 at 11:20

    What is missing? A Map implementation, eviction policies and disk storage. All non-trivial but planned.

    ReplyDelete

Post a Comment

Popular posts from this blog

Java is Very Fast, If You Don’t Create Many Objects

Image
  You still have to watch how many objects you create. This article looks at a benchmark passing events over TCP/IP at 4 billion events per minute using the net.openhft.chronicle.wire.channel package in Chronicle Wire and why we still avoid object allocations..  One of the key optimisations is creating almost no garbage. Allocation is a very cheap operation and collection of very short-lived objects is also very cheap. Does this really make a difference? What difference does one small object per event (44 bytes) make to the performance in a throughput test where GC pauses are amortised? While allocation is as efficient as possible, it doesn’t avoid the memory pressure on the L1/L2 caches of your CPUs and when many cores are busy, they are contending for memory in the shared L3 cache.  Results Benchmark on a Ryzen 5950X with Ubuntu 22.10. JVM Vendor, Version No objects Throughput, Average Latency* One object per event Throughput, Average Latency* Azul Zulu 1.8.0_322 60.6 ...
Read more

System wide unique nanosecond timestamps

A Unique Identifier can be very useful for tracing. Those ids are even more useful when they contain a high-resolution timestamp.  Not only do they record the time of an event, but if unique can help trace events as they pass through the system. Such unique timestamps however can be expensive depending on how they are implemented.   This post explores a lightweight means of producing a unique, monotonically increasing system-wide nano-second resolution timestamp available in our open-source library. Uses for Unique Identifiers Unique identifiers can be useful to associate with a piece of information so that information can be referred to later unambiguously. This could be an event, a request, an order id, or a customer id. They can naturally be used as a primary key in a database or key/value store to retrieve that information later. One of the challenges of generating these identifiers is avoiding creating duplicates while not having an increasing cost.  You could ...
Read more

What does Chronicle Software do?

Image
Overview Chronicle Software is about simplifying fast data.  It is a suite of libraries to make it easier to write, monitor and tune data processing systems where performance and scalability are concerned. But its free, how do you make money, through support? We offer premium support . However, we often hear from users for the first time about a year after they have it in production.  Most users find they can support the software themselves.  It is only after a year or so, they have questions or concerns about where to take the product next.  In many cases, it is to a problem we have already solved and they just need to upgrade their software or use a new module we have added. As we don't know who is using most of our software, we can't advise them on how best to use our software and what updates or enhancements they would benefit from. We need users to contact us and ask questions.  We have a free forum , and we respond to 50% of questions in 2 hours...
Read more