JDOM 2.0.6.1 · org.jdom2.StringBin

This is a mechanism for storing and reusing unique instances of Strings. The idea is that in XML the tag names, attribute names, and other String content is often repeated a lot. Each repeat is typically done as a new String instance. This class makes it possible to substantially reduce memory usage by reusing String instances instead of keeping the new ones.

This class is not the same as String.intern() because String.intern() uses the PermGen memory space (very limited in size), whereas this uses the heap.

The primary goal of this class is to be as memory efficient as possible. This has the interesting side effect of reducing the amount of time spent in garbage-collection cycles. While this does increase the amount of time to process a String, it means that subsequent String values can be 'recycled' fast, and, ideally, never need to leave the 'eden space' in the memory model which in turn means that the duplicate strings do not even hit the GC overhead. It is easy to measure that this process takes longer than simply keeping the duplicate String values, but it is much harder to measure the decreased cost of GC. It would be somewhat fair to say that the memory benefit is substantial, and the cost of allocation is offset by the savings in garbage collection. This trade-off is dependent on the amount of duplicate data you have. In XML where there are lots of repeating patterns of element and attribute names this can add up pretty fast.

This class is not thread-safe.

Field Summary

Modifier and Type	Field and Description
private String[][]	buckets The actual buckets.
private static final int	DEFAULTCAP How many buckets to start with Actually, this just sets the initial capacity which is used to calculate the number of buckets.
private static final int	GROW Default bucket-size growth factor
private int[]	lengths
private int	mask The bit mask and bit shift
private static final int	MAXBUCKET How big to let the largest bucket grow before a rehash

Constructor Summary

Access	Constructor and Description
public	StringBin() Create a default instance of the StringBin with the default capacity.
public	StringBin(int the capacity to set. capacity) Create a StringBin instance with a specified initial capacity.

Method Summary

Modifier and Type	Method and Description
private static final String	Returns: a Compacted version of the String. compact(final String The String to compact input) Compact a Java String to its smallest char[] backing array.
private final int	locate(final int hash, final String value, final String[] bucket, final int length) This code effectively does a binary search for a value.
private void	rehash() Store the existing values in a new and larger set of buckets.
public String	Returns: a String that is equals() to the input value, or null if the input was null reuse(final String The value to check. value) Get a String instance that is equal to the input value.
public int	Returns: the number of registered String values. size() Number of registered Strings

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

buckets	back to summary
private String[][] buckets The actual buckets. There is a really good reason to use a two-dimensional array: a 1 dimensional array would require us to do an inordinate amount of shifting of the data as we insert new values in to the middle. By having 'x' number of buckets, the average shift would be 1/x th of the amount, which is much faster.

DEFAULTCAP	back to summary
private static final int DEFAULTCAP How many buckets to start with Actually, this just sets the initial capacity which is used to calculate the number of buckets. This implementation will turn the default capacity of 1023 in to

DEFAULTCAP

back to summary

private static final int DEFAULTCAP

How many buckets to start with

Actually, this just sets the initial capacity which is used to calculate the number of buckets. This implementation will turn the default capacity of 1023 in to

GROW	back to summary
private static final int GROW Default bucket-size growth factor

lengths	back to summary
private int[] lengths

mask	back to summary
private int mask The bit mask and bit shift

MAXBUCKET	back to summary
private static final int MAXBUCKET How big to let the largest bucket grow before a rehash

Constructor Detail

StringBin	back to summary
public StringBin() Create a default instance of the StringBin with the default capacity.

StringBin	back to summary
public StringBin(int capacity) Create a StringBin instance with a specified initial capacity. Parameters capacity:int the capacity to set.

StringBin

back to summary

public StringBin(int capacity)

Create a StringBin instance with a specified initial capacity.

Parameters

capacity:int: the capacity to set.

Method Detail

compact	back to summary
private static final String compact(final String input) Compact a Java String to its smallest char[] backing array. Java often reuses the char[] array that backs String classes. If you have one String value and substring it, or some other methods, then instead of creating a new char[] array it reuses the original one. This can lead to small String values being backed by very large arrays. We do not want to be caching these large arrays... just the smallest. Parameters input:String The String to compact Returns:String a Compacted version of the String.

compact

back to summary

private static final String compact(final String input)

Compact a Java String to its smallest char[] backing array. Java often reuses the char[] array that backs String classes. If you have one String value and substring it, or some other methods, then instead of creating a new char[] array it reuses the original one. This can lead to small String values being backed by very large arrays. We do not want to be caching these large arrays... just the smallest.

Parameters

input:String: The String to compact

Returns:String

a Compacted version of the String.

locate	back to summary
private final int locate(final int hash, final String value, final String[] bucket, final int length) This code effectively does a binary search for a value. The order of the data in a bucket is increasing-by-hashcode, and then for values with the same hashcode, it is increasing by alphabetical.

rehash	back to summary
private void rehash() Store the existing values in a new and larger set of buckets. This reduces the number of values in each bucket, which improves insert time. The data is stored in hashCode() order, and then alphabetically for those instances where two String values have the same hashCode(). The bucketing hash key is calculated in a specific way that guarantees that when we rehash there values in a bucket will be divided between a new set of buckets, and no other source bucket will ever add values to a bucket that we are dividing our bucket to. The combination of the bucket hash key, and the bucket ordering means that during a rehash we never have to insert values in to the middle of the bucket.

rehash

back to summary

private void rehash()

Store the existing values in a new and larger set of buckets. This reduces the number of values in each bucket, which improves insert time.

The data is stored in hashCode() order, and then alphabetically for those instances where two String values have the same hashCode().

The bucketing hash key is calculated in a specific way that guarantees that when we rehash there values in a bucket will be divided between a new set of buckets, and no other source bucket will ever add values to a bucket that we are dividing our bucket to.

The combination of the bucket hash key, and the bucket ordering means that during a rehash we never have to insert values in to the middle of the bucket.

reuse	back to summary
public String reuse(final String value) Get a String instance that is equal to the input value. This may or may not be the same instance as the input value. Null input values will reuse() as null. Parameters value:String The value to check. Returns:String a String that is equals() to the input value, or null if the input was null

reuse

back to summary

public String reuse(final String value)

Get a String instance that is equal to the input value. This may or may not be the same instance as the input value. Null input values will reuse() as null.

Parameters

value:String: The value to check.

Returns:String

a String that is equals() to the input value, or null if the input was null

size	back to summary
public int size() Number of registered Strings Returns:int the number of registered String values.

size

back to summary

public int size()

Number of registered Strings

Returns:int: the number of registered String values.

pack-priv final Class StringBin

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail