Загрузка simdcomp - Загрузка исходного кода simdcomp

simdcomp

Исходный код С#

version 0.1.1

Скачать

Библиотека SIMDComp

Простая библиотека C для сжатия списков целых чисел с использованием двоичной упаковки и инструкций SIMD. Предполагается, что либо у вас есть список 32-битных целых чисел, большинство из которых малы, либо список 32-битных целых чисел, в котором различия между последовательными целыми числами малы. Ни одно программное обеспечение не способно надежно сжать массив 32-битных случайных чисел.

Эта библиотека может декодировать не менее 4 миллиардов сжатых целых чисел в секунду на большинстве процессоров настольных компьютеров или ноутбуков. То есть он может распаковывать данные со скоростью 15 ГБ/с. Это значительно быстрее, чем обычные кодеки, такие как gzip, LZO, Snappy или LZ4.

На процессоре Intel Skylake он может декодировать целые числа со скоростью 0,3 цикла на целое число, что может легко преобразовать в более чем 8 декодированных миллиардов целых чисел в секунду.

Эта библиотека является частью списка ресурсов C Awesome C.

Авторы: Дэниел Лемир, Натан Курц, Кристоф Рупп, Анатол Бельски, Ник Уайт и другие.

Для чего это нужно?

Это низкоуровневая библиотека для быстрого сжатия целых чисел. По своей конструкции он не определяет сжатый формат. Создание сжатого формата остается задачей (искушённого) пользователя.

Его используют:

upscaledb
EventQL
МантикораПоиск

Требования

Ваш процессор должен поддерживать SSE4.1 (он поддерживается большинством процессоров Intel и AMD, выпущенных с 2008 года).
Можно создать основную часть кода, если ваш процессор поддерживает SSE2 (Pentium4 или выше).
C99-совместимый компилятор (предполагается GCC)
Linux-подобный дистрибутив предполагается в make-файле.

Для простой версии C, которая не использует инструкции SIMD, см. https://github.com/lemire/LittleIntPacker.

Использование

Сжатие работает с блоками из 128 целых чисел.

Полный рабочий пример см. в файле example.c (его можно собрать и запустить с помощью команды «make example; ./example»).

Списки целых чисел в случайном порядке.

 const uint32_t b = maxbits ( datain ); // computes bit width
simdpackwithoutmask ( datain , buffer , b ); //compressed to buffer, compressing 128 32-bit integers down to b*32 bytes
simdunpack ( buffer , backbuffer , b ); //uncompressed to backbuffer

При чтении 128 32-битных целых чисел записывается только b 128-битных слов. Таким образом, степень сжатия равна 32/b.

Сортированные списки целых чисел.

Мы использовали дифференциальное кодирование: сохраняем разницу между последовательными целыми числами. Для этой цели нам нужно начальное значение (называемое смещением).

 uint32_t offset = 0 ;
uint32_t b1 = simdmaxbitsd1 ( offset , datain ); // bit width
simdpackwithoutmaskd1 ( offset , datain , buffer , b1 ); //compressing 128 32-bit integers down to b1*32 bytes
simdunpackd1 ( offset , buffer , backbuffer , b1 ); //uncompressed

Общий пример для массивов произвольной длины:

 int compress_decompress_demo () {
  size_t k , N = 9999 ;
  __m128i * endofbuf ;
  uint32_t * datain = malloc ( N * sizeof ( uint32_t ));
  uint8_t * buffer ;
  uint32_t * backbuffer = malloc ( N * sizeof ( uint32_t ));
  uint32_t b ;

  for ( k = 0 ; k < N ; ++ k ){        /* start with k=0, not k=1! */
    datain [ k ] = k ;
  }

  b = maxbits_length ( datain , N );
  buffer = malloc ( simdpack_compressedbytes ( N , b )); // allocate just enough memory
  endofbuf = simdpack_length ( datain , N , ( __m128i * ) buffer , b );
  /* compressed data is stored between buffer and endofbuf using (endofbuf-buffer)*sizeof(__m128i) bytes */
  /* would be safe to do : buffer = realloc(buffer,(endofbuf-(__m128i *)buffer)*sizeof(__m128i)); */
  simdunpack_length (( const __m128i * ) buffer , N , backbuffer , b );

  for ( k = 0 ; k < N ; ++ k ){
    if ( datain [ k ] != backbuffer [ k ]) {
      printf ( "bugn" );
      return -1 ;
    }
  }
  return 0 ;
}

Система отсчета

У нас также есть функции системы координат (FOR) (см. заголовок simdfor.h). Они работают как процедуры упаковки битов, но не используют дифференциальное кодирование, поэтому в некоторых случаях позволяют ускорить поиск за счет сжатия.

Настраивать

сделать тест

и если ты смеешь:

сделать установку

Идти

Если вы являетесь пользователем go, есть папка go, где вы найдете простую демонстрацию.

Другие библиотеки

Быстрое сжатие целых чисел в Go: https://github.com/ronanh/intcomp
Алгоритмы быстрой распаковки битов: порт Simdcomp на Rust https://github.com/quickwit-oss/bitpacking
SIMDCompressionAndIntersection: библиотека C++ для сжатия и пересечения отсортированных списков целых чисел с использованием инструкций SIMD https://github.com/lemire/SIMDCompressionAndIntersection.
Библиотека FastPFOR C++: быстрое сжатие целых чисел https://github.com/lemire/FastPFor
Высокопроизводительное словарное кодирование https://github.com/lemire/dictionary
LittleIntPacker: библиотека C для максимально быстрой упаковки и распаковки коротких массивов целых чисел https://github.com/lemire/LittleIntPacker
StreamVByte: быстрое сжатие целых чисел в C с использованием кодека StreamVByte https://github.com/lemire/streamvbyte.
MaskedVByte: быстрый декодер целых чисел, сжатых VByte https://github.com/lemire/MaskedVByte
CSharpFastPFOR: библиотека сжатия целых чисел AC# https://github.com/Genbox/CSharpFastPFOR
JavaFastPFOR: библиотека сжатия целых чисел Java https://github.com/lemire/JavaFastPFOR
Кодирование: библиотеки сжатия целых чисел для Go https://github.com/zhenjl/encoding
FrameOfReference — это библиотека C++, предназначенная для сжатия кадров (FOR): https://github.com/lemire/FrameOfReference.
libvbyte: быстрая реализация 32-битного/64-битного целочисленного сжатия varbyte https://github.com/cruppstahl/libvbyte.
TurboPFor — это библиотека C, предлагающая множество интересных оптимизаций. Определенно стоит проверить! (лицензия GPL) https://github.com/powturbo/TurboPFor
Oroch — это библиотека C++, предлагающая удобный API (лицензия MIT) https://github.com/ademkov/Oroch.

Другие языки программирования

Есть обертка для Юлии.
Есть порт на Rust.

Ссылки

Дэниел Лемир, Натан Курц, Кристоф Рупп, Stream VByte: более быстрое байт-ориентированное сжатие целых чисел, Information Processing Letters, Information Processing Letters 130, февраль 2018 г., страницы 1–6 https://arxiv.org/abs/1709.08990
Цзянго Ван, Чунбин Линь, Яннис Папаконстантину, Стивен Суонсон, Экспериментальное исследование сжатия растровых изображений в сравнении со сжатием инвертированных списков, SIGMOD 2017 http://db.ucsd.edu/wp-content/uploads/2017/03/sidm338-wangA. PDF
П. Дамм, Д. Хабих, Дж. Хильдебрандт, В. Ленер, Облегченные алгоритмы сжатия данных: экспериментальный обзор (эксперименты и анализ), EDBT 2017 http://openproceedings.org/2017/conf/edbt/paper-146. PDF
П. Дамм, Д. Хабих, Дж. Хильдебрандт, В. Ленер, «Сравнительная оценка облегченных алгоритмов сжатия данных», EDBT 2017 http://openproceedings.org/2017/conf/edbt/paper-414.pdf
Дэниел Лемир, Леонид Бойцов, Натан Курц, SIMD-сжатие и пересечение отсортированных целых чисел, Практика и опыт разработки программного обеспечения 46 (6) 2016. http://arxiv.org/abs/1401.6399
Дэниел Лемир и Леонид Бойцов, Декодирование миллиардов целых чисел в секунду посредством векторизации, Software Practice & Experience 45 (1), 2015. http://arxiv.org/abs/1209.2137 http://onlinelibrary.wiley.com/doi/10.1002 /spe.2203/аннотация
Джефф Плезанс, Натан Курц, Дэниел Лемир, Векторизованное декодирование VByte, Международный симпозиум по веб-алгоритмам 2015, 2015. http://arxiv.org/abs/1503.07387
Уэйн Синь Чжао, Сюдун Чжан, Дэниел Лемир, Дондонг Шань, Цзянь-Юнь Не, Хунфэй Ян, Цзи-Ронг Вэнь, Общий подход на основе SIMD к ускорению алгоритмов сжатия, Транзакции ACM в информационных системах 33 (3), 2015. http ://arxiv.org/abs/1502.01916
Т.Д. Ву, Методы битовой упаковки для индексации геномов: I. Хэш-таблицы, Алгоритмы молекулярной биологии 11 (5), 2016. http://almob.biomedcentral.com/articles/10.1186/s13015-016-0069-5

Расширять

Дополнительная информация