<commit_before>// Copyright (c) 2012 Microsoft Corporation.  All rights reserved.
package tlc2.tool.fp;

import java.io.EOFException;
import java.io.IOException;
import java.io.RandomAccessFile;
import java.lang.reflect.Field;
import java.nio.LongBuffer;
import java.rmi.RemoteException;
import java.util.Arrays;
import java.util.NoSuchElementException;
import java.util.TreeSet;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

import sun.misc.Unsafe;
import tlc2.output.EC;
import tlc2.tool.fp.MSBDiskFPSet.TLCIterator;
import util.Assert;

@SuppressWarnings({ "serial", "restriction" })
public class OffHeapDiskFPSet extends DiskFPSet implements FPSetStatistic {
	
	private static sun.misc.Unsafe getUnsafe() {
		try {
			Field f = sun.misc.Unsafe.class.getDeclaredField("theUnsafe");
			f.setAccessible(true);
			return (sun.misc.Unsafe) f.get(null);
		} catch (Exception e) {
			//TODO handle if non-sun vm
			return null;
		}
	}
	
	protected static final long BucketBaseIdx = 0xFFFFFFFFFFFFFFFFL - (InitialBucketCapacity - 1);

	/**
	 * 
	 */
	private final Unsafe u;
	
	/**
	 * The base address allocated for fingerprints
	 */
	private final long baseAddress;
	
	/**
	 * Address size (either 4 or 8 bytes) depending on current architecture
	 */
	private final int logAddressSize;

	/**
	 * A bucket containing collision elements which is used as a fall-back if a
	 * bucket is fully used up. Buckets cannot grow as the whole in-memory
	 * data-structure is static and not designed to be resized.
	 * 
	 * <p>
	 * Open addressing - contrary to separate chaining - is not an option for an
	 * {@link OffHeapDiskFPSet}, because it does not support the invariant of
	 * monotonic increasing buckets required by the {@link Indexer}. Adhering to
	 * this invariant has the benefit, that only the elements in a bucket have
	 * to be sorted, but they don't change buckets during sort. Thus, a
	 * temporary sort array as in {@link LSBDiskFPSet.LSBFlusher#prepareTable()} is
	 * obsolete halving the memory footprint.
	 * </p>
	 */
	protected CollisionBucket collisionBucket;
	
	/**
	 * The indexer maps a fingerprint to a in-memory bucket and the associated lock
	 */
	private final Indexer indexer;
	
	private final ReadWriteLock csRWLock = new ReentrantReadWriteLock();

	protected OffHeapDiskFPSet(long maxInMemoryCapacity) throws RemoteException {
		this(maxInMemoryCapacity, 0);
	}
	
	protected OffHeapDiskFPSet(final long maxInMemoryCapacity, final int prefixBits) throws RemoteException {
		super(maxInMemoryCapacity);
		
		// Determine base address which varies depending on machine architecture.
		u = getUnsafe();
		int addressSize = u.addressSize();
		int cnt = -1;
		while (addressSize > 0) {
			cnt++;
			addressSize = addressSize >>> 1; // == (n/2)
		}
		logAddressSize = cnt;

		// Allocate non-heap memory for maxInMemoryCapacity fingerprints
		long bytes = maxInMemoryCapacity << logAddressSize;
		baseAddress = u.allocateMemory(bytes);
		
		// Null memory (could be done in parallel on segments when bottleneck).
		// This is essential as allocateMemory returns uninitialized memory and
		// memInsert/memLockup utilize 0L as a mark for an unused fingerprint slot.
		// Otherwise memory garbage wouldn't be distinguishable from a true fp. 
		for (long i = 0; i < maxInMemoryCapacity; i++) {
			u.putAddress(log2phy(i), 0L);
		}

		this.collisionBucket = new CollisionBucket();
		
		this.flusher = new OffHeapMSBFlusher();
		
		
		// Calculate Hamming weight of maxInMemoryCapacity
		final int bitCount = Long.bitCount(maxInMemoryCapacity);
		
		// If Hamming weight is 1, the logical index address can be calculated
		// significantly faster by bit-shifting. However, with large memory
		// sizes, only supporting increments of 2^n sizes would waste memory
		// (e.g. either 32GiB or 64Gib). Hence we check if the bitCount allows
		// us to use bit-shifting and fall back to less efficient modulo otherwise.
		if (bitCount == 1) {
			this.indexer = new BitshiftingIndexer(maxInMemoryCapacity, prefixBits);
		} else {
			this.indexer = new Indexer(prefixBits);
		}
	}
	
	/* (non-Javadoc)
	 * @see tlc2.tool.fp.FPSet#size()
	 */
	public final long size() {
		return super.size() + collisionBucket.size();
	}

	/* (non-Javadoc)
	 * @see tlc2.tool.fp.DiskFPSet#sizeof()
	 */
	public long sizeof() {
		//TODO needs locking?
		long size = 44; // approx size of this DiskFPSet object
		size += maxTblCnt * (long) LongSize;
		size += getIndexCapacity() * 4;
		size += collisionBucket.size() * (long) LongSize; // ignoring the internal TreeSet overhead here
		return size;<commit_msg>Rollback "Override size to take collision bucket into account"<commit_after>// Copyright (c) 2012 Microsoft Corporation.  All rights reserved.
package tlc2.tool.fp;

import java.io.EOFException;
import java.io.IOException;
import java.io.RandomAccessFile;
import java.lang.reflect.Field;
import java.nio.LongBuffer;
import java.rmi.RemoteException;
import java.util.Arrays;
import java.util.NoSuchElementException;
import java.util.TreeSet;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

import sun.misc.Unsafe;
import tlc2.output.EC;
import tlc2.tool.fp.MSBDiskFPSet.TLCIterator;
import util.Assert;

@SuppressWarnings({ "serial", "restriction" })
public class OffHeapDiskFPSet extends DiskFPSet implements FPSetStatistic {
	
	private static sun.misc.Unsafe getUnsafe() {
		try {
			Field f = sun.misc.Unsafe.class.getDeclaredField("theUnsafe");
			f.setAccessible(true);
			return (sun.misc.Unsafe) f.get(null);
		} catch (Exception e) {
			//TODO handle if non-sun vm
			return null;
		}
	}
	
	protected static final long BucketBaseIdx = 0xFFFFFFFFFFFFFFFFL - (InitialBucketCapacity - 1);

	/**
	 * 
	 */
	private final Unsafe u;
	
	/**
	 * The base address allocated for fingerprints
	 */
	private final long baseAddress;
	
	/**
	 * Address size (either 4 or 8 bytes) depending on current architecture
	 */
	private final int logAddressSize;

	/**
	 * A bucket containing collision elements which is used as a fall-back if a
	 * bucket is fully used up. Buckets cannot grow as the whole in-memory
	 * data-structure is static and not designed to be resized.
	 * 
	 * <p>
	 * Open addressing - contrary to separate chaining - is not an option for an
	 * {@link OffHeapDiskFPSet}, because it does not support the invariant of
	 * monotonic increasing buckets required by the {@link Indexer}. Adhering to
	 * this invariant has the benefit, that only the elements in a bucket have
	 * to be sorted, but they don't change buckets during sort. Thus, a
	 * temporary sort array as in {@link LSBDiskFPSet.LSBFlusher#prepareTable()} is
	 * obsolete halving the memory footprint.
	 * </p>
	 */
	protected CollisionBucket collisionBucket;
	
	/**
	 * The indexer maps a fingerprint to a in-memory bucket and the associated lock
	 */
	private final Indexer indexer;
	
	private final ReadWriteLock csRWLock = new ReentrantReadWriteLock();

	protected OffHeapDiskFPSet(long maxInMemoryCapacity) throws RemoteException {
		this(maxInMemoryCapacity, 0);
	}
	
	protected OffHeapDiskFPSet(final long maxInMemoryCapacity, final int prefixBits) throws RemoteException {
		super(maxInMemoryCapacity);
		
		// Determine base address which varies depending on machine architecture.
		u = getUnsafe();
		int addressSize = u.addressSize();
		int cnt = -1;
		while (addressSize > 0) {
			cnt++;
			addressSize = addressSize >>> 1; // == (n/2)
		}
		logAddressSize = cnt;

		// Allocate non-heap memory for maxInMemoryCapacity fingerprints
		long bytes = maxInMemoryCapacity << logAddressSize;
		baseAddress = u.allocateMemory(bytes);
		
		// Null memory (could be done in parallel on segments when bottleneck).
		// This is essential as allocateMemory returns uninitialized memory and
		// memInsert/memLockup utilize 0L as a mark for an unused fingerprint slot.
		// Otherwise memory garbage wouldn't be distinguishable from a true fp. 
		for (long i = 0; i < maxInMemoryCapacity; i++) {
			u.putAddress(log2phy(i), 0L);
		}

		this.collisionBucket = new CollisionBucket();
		
		this.flusher = new OffHeapMSBFlusher();
		
		
		// Calculate Hamming weight of maxInMemoryCapacity
		final int bitCount = Long.bitCount(maxInMemoryCapacity);
		
		// If Hamming weight is 1, the logical index address can be calculated
		// significantly faster by bit-shifting. However, with large memory
		// sizes, only supporting increments of 2^n sizes would waste memory
		// (e.g. either 32GiB or 64Gib). Hence we check if the bitCount allows
		// us to use bit-shifting and fall back to less efficient modulo otherwise.
		if (bitCount == 1) {
			this.indexer = new BitshiftingIndexer(maxInMemoryCapacity, prefixBits);
		} else {
			this.indexer = new Indexer(prefixBits);
		}
	}

	/* (non-Javadoc)
	 * @see tlc2.tool.fp.DiskFPSet#sizeof()
	 */
	public long sizeof() {
		//TODO needs locking?
		long size = 44; // approx size of this DiskFPSet object
		size += maxTblCnt * (long) LongSize;
		size += getIndexCapacity() * 4;
		size += collisionBucket.size() * (long) LongSize; // ignoring the internal TreeSet overhead here
		return size;
{'fraction_non_alphanumeric': 0.09216239687364307, 'fraction_numerical': 0.006838905775075988, 'mean_word_length': 3.8591772151898733, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 15, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 2, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4222149', 'n_tokens_mistral': 3001, 'n_tokens_neox': 2678, 'n_words': 949}