Buckets:

agent-collaborations
/

hutter-prize-67

Files

xet

agent-collaborations/hutter-prize-67 / decoder-bundle-minimization /work /paq8px-src /src /Bucket16.hpp

soixantesept

about 1 month ago

download

raw

7.23 kB

﻿#pragma once

#include <cstdint>
#include <cstring>
#include <type_traits>
#include "Random.hpp"
#include "HashElementForContextMap.hpp"
#include "HashElementForStationaryMap.hpp"
#include "HashElementForBitHistoryState.hpp"

/**
 * Hash bucket to be used in a hash table
 * A hash bucket consists of a list of HashElements
 * Each hash element consists of a 16-bit checksum for collision detection
 * and an arbitrary-sized value:
 *   For HashElementForBitHistoryState: one bit-history byte   ( sizeof(HashElement) = 2+1 = 3 bytes )
 *   For LargeStationaryMap: two 16-bit counts                 ( sizeof(HashElement) = 2+4 = 6 bytes )
 *   For LargeIndirectContext: byte history (usually 4 bytes)  ( sizeof(HashElement) = 2+4 = 6 bytes )
 *   For ContextMap and ContextMap2: bit and byte statistics   ( sizeof(HashElement) = 2+7 = 9 bytes )
 *
 */

#pragma pack(push,1)
template<typename T>
struct HashElement {
  uint16_t checksum;
  T value;
};
#pragma pack(pop)

template<typename T, int ElementsInBucket>
class Bucket16 {
private:
  HashElement<T> elements[ElementsInBucket];

  // Optimized memmove with known parameters
  // Original:
  //  memmove(&elements[1], &elements[0], i * sizeof(HashElement<T>));
  // Optimized:
  // Implementation: iterate over compile-time indices (N-1 down to 0).
  // Each copy is guarded at runtime by `count`, but the loop itself is
  // fully unrolled by the compiler - no branch on the loop counter.
  // It translates to a series of (fully unrolled) 'mov' intructions.
  //
  // Is = { 0, 1, ..., ElementsInBucket-2 }
  // We copy element[N-1-Is] <- element[N-2-Is] for each Is where
  // (N-1-Is) <= count, i.e. we copy the last `count` positions right by 1.
  template<size_t... Is>
  ALWAYS_INLINE
  void shiftImpl(size_t count, std::index_sequence<Is...>) noexcept {
    // Fold expression : each clause is evaluated in order(left - to - right comma).
    // The copy only executes when the destination index falls within [1, count].
    ((Is < ElementsInBucket - 1 && (ElementsInBucket - 1 - Is) <= count
    ? (elements[ElementsInBucket - 1 - Is] = elements[ElementsInBucket - 2 - Is], 0)
    : 0), ...);
  }

  ALWAYS_INLINE
  void shiftElementsRight(size_t count) noexcept {
    shiftImpl(count, std::make_index_sequence<ElementsInBucket - 1>{});
  }

public:

  void reset() {
    for (size_t i = 0; i < ElementsInBucket; i++)
      elements[i] = {};
  }

  void stat(uint64_t& used, uint64_t& empty) {
    for (size_t i = 0; i < ElementsInBucket; i++)
      if (elements[i].checksum == 0)
        empty++;
      else
        used++;
  }
    
  T* find(uint16_t checksum, Random* rnd) {

    checksum += checksum == 0; //don't allow 0 checksums (0 checksums are used for empty slots)

    if (elements[0].checksum == checksum) //there is a high chance that we'll find it in the first slot, so go for it
      return &elements[0].value;

    for (size_t i = 1; i < ElementsInBucket; ++i) { //note: gcc fully unrolls this loop: it gives a tiny speed improvement for a cost of ~4K exe size
      const uint16_t thisChecksum = elements[i].checksum;
      if (thisChecksum == checksum) { // found matching checksum
        //shift elements down and move matching element to front
        HashElement<T> tmpElement = elements[i];
        shiftElementsRight(i);
        elements[0] = tmpElement;
        return &elements[0].value;
      }
      if (thisChecksum == 0) { // found empty slot
        //shift elements down by 1 (make room for the new element in the first slot)
        shiftElementsRight(i);
        elements[0].checksum = checksum;
        elements[0].value = {};
        return &elements[0].value;
      }
    }

    //no match and no empty slot -> overwrite an existing element with the new (empty) one

    //Replacement strategy:
    // - In case the hash elements represent an indirect context (we have content but no priority): overwrite the last used element
    // - In case the hash elements are counts/statistics: overwrite one of the the last used elements having low priority.
    //
    //   The priority of an element is established by the counts it represents: large counts usually mean that the element is worthy to keep.
    //   When an element is accessed recently it is probably worthy to keep as it represents recent statistics,
    //   when an element is accessed long ago it is probably obolete and may be overwritten.
    //   In order to keep track of the order the elements were accessed we move the most recently accessed element to the front: thus
    //   recently acessed elements are usually somewhere in the front of the bucket, rarely accessed element slowly move to the back. The
    //   last elements in the bucket are cantidates for eviction.
    //
    //   Overwriting the lowest priority element (with no regard of its position) is in favor of homogenous (semi-stationary) files.
    //   Overwriting the last element (with no regard of its priority) is in favor of mixed-content files.
    //   In order to favor both, we are using a probabilistic replacement startegy where most recently accessed and/or higher priority
    //   elements have higher chance to stay in the bucket = rarely accessed and/or low priority elements have higher chance to be 
    //   evicted (overwritten).
    //
    //   The 2 most recently accessed elements are always protected from overwriting.
    
    size_t minElementIdx = ElementsInBucket - 1; //index of element to be evicted
    if constexpr (std::is_same<T, HashElementForContextMap>::value ||
                  std::is_same<T, HashElementForStationaryMap>::value || 
                  std::is_same<T, HashElementForBitHistoryState>::value)
    {
      uint32_t RND = rnd->operator()(32); //note: we'll need only 4 times 6 = 24 bits
      if ((RND & 63) >= 1) {
        uint32_t minPrio = elements[ElementsInBucket - 1].value.prio();
        uint32_t thisPrio = elements[ElementsInBucket - 2].value.prio();
        if (thisPrio < minPrio) {
          minPrio = thisPrio;
          minElementIdx = ElementsInBucket - 2;
        }
        RND >>= 6;
        if ((RND & 63) >= 4) {
          thisPrio = elements[ElementsInBucket - 3].value.prio();
          if (thisPrio < minPrio) {
            minPrio = thisPrio;
            minElementIdx = ElementsInBucket - 3;
          }
          RND >>= 6;
          if ((RND & 63) >= 8) {
            thisPrio = elements[ElementsInBucket - 4].value.prio();
            if (thisPrio < minPrio) {
              minPrio = thisPrio;
              minElementIdx = ElementsInBucket - 4;
            }
            RND >>= 6;
            if ((RND & 63) >= 16) {
              thisPrio = elements[ElementsInBucket - 5].value.prio();
              if (thisPrio < minPrio) {
                minPrio = thisPrio;
                minElementIdx = ElementsInBucket - 5;
              }
            }
          }
        }
      }
    }

    //shift elements down by 1 (make room for the new element in the first slot)
    //at the same time owerwrite the element at position "minElementIdx" (the element to be evicted)
    shiftElementsRight(minElementIdx);
    elements[0].checksum = checksum;
    elements[0].value = {};
    return &elements[0].value;
  }
};

Xet Storage Details

Size:: 7.23 kB
Xet hash:: 3fe830c10b8372bf89a0385ffbdd805dee237efe6d041beba841c1bf22cef2c0

Xet efficiently stores files, intelligently splitting them into unique chunks and accelerating uploads and downloads. More info.

	#pragma once

	#include <cstdint>
	#include <cstring>
	#include <type_traits>
	#include "Random.hpp"
	#include "HashElementForContextMap.hpp"
	#include "HashElementForStationaryMap.hpp"
	#include "HashElementForBitHistoryState.hpp"

	/**
	* Hash bucket to be used in a hash table
	* A hash bucket consists of a list of HashElements
	* Each hash element consists of a 16-bit checksum for collision detection
	* and an arbitrary-sized value:
	* For HashElementForBitHistoryState: one bit-history byte ( sizeof(HashElement) = 2+1 = 3 bytes )
	* For LargeStationaryMap: two 16-bit counts ( sizeof(HashElement) = 2+4 = 6 bytes )
	* For LargeIndirectContext: byte history (usually 4 bytes) ( sizeof(HashElement) = 2+4 = 6 bytes )
	* For ContextMap and ContextMap2: bit and byte statistics ( sizeof(HashElement) = 2+7 = 9 bytes )
	*
	*/

	#pragma pack(push,1)
	template<typename T>
	struct HashElement {
	uint16_t checksum;
	T value;
	};
	#pragma pack(pop)

	template<typename T, int ElementsInBucket>
	class Bucket16 {
	private:
	HashElement<T> elements[ElementsInBucket];

	// Optimized memmove with known parameters
	// Original:
	// memmove(&elements[1], &elements[0], i * sizeof(HashElement<T>));
	// Optimized:
	// Implementation: iterate over compile-time indices (N-1 down to 0).
	// Each copy is guarded at runtime by `count`, but the loop itself is
	// fully unrolled by the compiler - no branch on the loop counter.
	// It translates to a series of (fully unrolled) 'mov' intructions.
	//
	// Is = { 0, 1, ..., ElementsInBucket-2 }
	// We copy element[N-1-Is] <- element[N-2-Is] for each Is where
	// (N-1-Is) <= count, i.e. we copy the last `count` positions right by 1.
	template<size_t... Is>
	ALWAYS_INLINE
	void shiftImpl(size_t count, std::index_sequence<Is...>) noexcept {
	// Fold expression : each clause is evaluated in order(left - to - right comma).
	// The copy only executes when the destination index falls within [1, count].
	((Is < ElementsInBucket - 1 && (ElementsInBucket - 1 - Is) <= count
	? (elements[ElementsInBucket - 1 - Is] = elements[ElementsInBucket - 2 - Is], 0)
	: 0), ...);
	}

	ALWAYS_INLINE
	void shiftElementsRight(size_t count) noexcept {
	shiftImpl(count, std::make_index_sequence<ElementsInBucket - 1>{});
	}

	public:

	void reset() {
	for (size_t i = 0; i < ElementsInBucket; i++)
	elements[i] = {};
	}

	void stat(uint64_t& used, uint64_t& empty) {
	for (size_t i = 0; i < ElementsInBucket; i++)
	if (elements[i].checksum == 0)
	empty++;
	else
	used++;
	}

	T* find(uint16_t checksum, Random* rnd) {

	checksum += checksum == 0; //don't allow 0 checksums (0 checksums are used for empty slots)

	if (elements[0].checksum == checksum) //there is a high chance that we'll find it in the first slot, so go for it
	return &elements[0].value;

	for (size_t i = 1; i < ElementsInBucket; ++i) { //note: gcc fully unrolls this loop: it gives a tiny speed improvement for a cost of ~4K exe size
	const uint16_t thisChecksum = elements[i].checksum;
	if (thisChecksum == checksum) { // found matching checksum
	//shift elements down and move matching element to front
	HashElement<T> tmpElement = elements[i];
	shiftElementsRight(i);
	elements[0] = tmpElement;
	return &elements[0].value;
	}
	if (thisChecksum == 0) { // found empty slot
	//shift elements down by 1 (make room for the new element in the first slot)
	shiftElementsRight(i);
	elements[0].checksum = checksum;
	elements[0].value = {};
	return &elements[0].value;
	}
	}

	//no match and no empty slot -> overwrite an existing element with the new (empty) one

	//Replacement strategy:
	// - In case the hash elements represent an indirect context (we have content but no priority): overwrite the last used element
	// - In case the hash elements are counts/statistics: overwrite one of the the last used elements having low priority.
	//
	// The priority of an element is established by the counts it represents: large counts usually mean that the element is worthy to keep.
	// When an element is accessed recently it is probably worthy to keep as it represents recent statistics,
	// when an element is accessed long ago it is probably obolete and may be overwritten.
	// In order to keep track of the order the elements were accessed we move the most recently accessed element to the front: thus
	// recently acessed elements are usually somewhere in the front of the bucket, rarely accessed element slowly move to the back. The
	// last elements in the bucket are cantidates for eviction.
	//
	// Overwriting the lowest priority element (with no regard of its position) is in favor of homogenous (semi-stationary) files.
	// Overwriting the last element (with no regard of its priority) is in favor of mixed-content files.
	// In order to favor both, we are using a probabilistic replacement startegy where most recently accessed and/or higher priority
	// elements have higher chance to stay in the bucket = rarely accessed and/or low priority elements have higher chance to be
	// evicted (overwritten).
	//
	// The 2 most recently accessed elements are always protected from overwriting.

	size_t minElementIdx = ElementsInBucket - 1; //index of element to be evicted
	if constexpr (std::is_same<T, HashElementForContextMap>::value \|\|
	std::is_same<T, HashElementForStationaryMap>::value \|\|
	std::is_same<T, HashElementForBitHistoryState>::value)
	{
	uint32_t RND = rnd->operator()(32); //note: we'll need only 4 times 6 = 24 bits
	if ((RND & 63) >= 1) {
	uint32_t minPrio = elements[ElementsInBucket - 1].value.prio();
	uint32_t thisPrio = elements[ElementsInBucket - 2].value.prio();
	if (thisPrio < minPrio) {
	minPrio = thisPrio;
	minElementIdx = ElementsInBucket - 2;
	}
	RND >>= 6;
	if ((RND & 63) >= 4) {
	thisPrio = elements[ElementsInBucket - 3].value.prio();
	if (thisPrio < minPrio) {
	minPrio = thisPrio;
	minElementIdx = ElementsInBucket - 3;
	}
	RND >>= 6;
	if ((RND & 63) >= 8) {
	thisPrio = elements[ElementsInBucket - 4].value.prio();
	if (thisPrio < minPrio) {
	minPrio = thisPrio;
	minElementIdx = ElementsInBucket - 4;
	}
	RND >>= 6;
	if ((RND & 63) >= 16) {
	thisPrio = elements[ElementsInBucket - 5].value.prio();
	if (thisPrio < minPrio) {
	minPrio = thisPrio;
	minElementIdx = ElementsInBucket - 5;
	}
	}
	}
	}
	}
	}

	//shift elements down by 1 (make room for the new element in the first slot)
	//at the same time owerwrite the element at position "minElementIdx" (the element to be evicted)
	shiftElementsRight(minElementIdx);
	elements[0].checksum = checksum;
	elements[0].value = {};
	return &elements[0].value;
	}
	};