หน้าแรก>การเขียนโปรแกรมที่เกี่ยวข้อง>ซอร์สโค้ด C#
ดาวน์โหลด

ไลบรารี SIMDComp

ไลบรารี C อย่างง่ายสำหรับการบีบอัดรายการจำนวนเต็มโดยใช้การบรรจุแบบไบนารีและคำสั่ง SIMD สมมติฐานก็คือคุณมีรายการจำนวนเต็ม 32 บิตซึ่งส่วนใหญ่มีขนาดเล็ก หรือรายการจำนวนเต็ม 32 บิตซึ่งความแตกต่างระหว่างจำนวนเต็มต่อเนื่องกันมีขนาดเล็ก ไม่มีซอฟต์แวร์ใดที่สามารถบีบอัดอาร์เรย์ของตัวเลขสุ่ม 32 บิตได้อย่างน่าเชื่อถือ

ไลบรารีนี้สามารถถอดรหัสจำนวนเต็มที่ถูกบีบอัดได้อย่างน้อย 4 พันล้านต่อวินาทีบนโปรเซสเซอร์เดสก์ท็อปหรือแล็ปท็อปส่วนใหญ่ นั่นคือสามารถขยายขนาดข้อมูลได้ในอัตรา 15 GB/s ซึ่งเร็วกว่าตัวแปลงสัญญาณทั่วไปเช่น gzip, LZO, Snappy หรือ LZ4 อย่างมาก

บนโปรเซสเซอร์ Skylake Intel สามารถถอดรหัสจำนวนเต็มได้ในอัตรา 0.3 รอบต่อจำนวนเต็ม ซึ่งสามารถแปลเป็นจำนวนเต็มที่ถูกถอดรหัสมากกว่า 8 พันล้านต่อวินาทีได้อย่างง่ายดาย

ไลบรารีนี้เป็นส่วนหนึ่งของรายการทรัพยากร C ของ Awesome C

ผู้ร่วมให้ข้อมูล: Daniel Lemire, Nathan Kurz, Christoph Rupp, Anatol Belski, Nick White และคนอื่นๆ

มีไว้เพื่ออะไร?

นี่คือไลบรารีระดับต่ำสำหรับการบีบอัดจำนวนเต็มอย่างรวดเร็ว โดยการออกแบบไม่ได้กำหนดรูปแบบการบีบอัด ขึ้นอยู่กับผู้ใช้ (ซับซ้อน) ในการสร้างรูปแบบการบีบอัด

มันถูกใช้โดย:

  • อัปสเกลdb
  • เหตุการณ์QL
  • มันติคอร์ค้นหา

ความต้องการ

  • โปรเซสเซอร์ของคุณควรรองรับ SSE4.1 (รองรับโดยโปรเซสเซอร์ Intel และ AMD ส่วนใหญ่ที่เปิดตัวตั้งแต่ปี 2551)
  • เป็นไปได้ที่จะสร้างส่วนหลักของโค้ดหากโปรเซสเซอร์ของคุณรองรับ SSE2 (Pentium4 หรือดีกว่า)
  • คอมไพเลอร์ที่สอดคล้องกับ C99 (ถือว่า GCC)
  • makefile จะถือว่าการกระจายแบบ Linux เหมือนกัน

สำหรับเวอร์ชัน C ธรรมดาที่ไม่ใช้คำแนะนำ SIMD โปรดดูhttps://github.com/lemire/LittleIntPacker

การใช้งาน

การบีบอัดทำงานบนบล็อกจำนวนเต็ม 128 จำนวน

สำหรับตัวอย่างการทำงานที่สมบูรณ์ โปรดดูที่ example.c (คุณสามารถสร้างและรันด้วย "make example; ./example")

  1. รายการจำนวนเต็มตามลำดับแบบสุ่ม 
 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

ในขณะที่อ่านจำนวนเต็ม 32 บิตจำนวน 128 ตัว แต่เขียนเพียงคำ b 128 บิตเท่านั้น ดังนั้นอัตราส่วนกำลังอัดคือ 32/b

  1. รายการเรียงลำดับของจำนวนเต็ม

เราใช้การเข้ารหัสแบบดิฟเฟอเรนเชียล: เราเก็บความแตกต่างระหว่างจำนวนเต็มต่อเนื่องกัน เพื่อจุดประสงค์นี้ เราจำเป็นต้องมีค่าเริ่มต้น (เรียกว่าออฟเซ็ต) 

 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 ;
}
  1. กรอบอ้างอิง

นอกจากนี้เรายังมีฟังก์ชัน frame-of-reference (FOR) (ดูส่วนหัว simdfor.h) มันทำงานเหมือนรูทีนการบรรจุบิต แต่ไม่ใช้การเข้ารหัสที่แตกต่างกัน เพื่อให้สามารถค้นหาได้เร็วขึ้นในบางกรณี โดยเสียค่าใช้จ่ายในการบีบอัด

ตั้งค่า

ทำแบบทดสอบ

และถ้าคุณกล้า:

ทำการติดตั้ง

ไป

หากคุณเป็นผู้ใช้ go จะมีโฟลเดอร์ "go" ที่คุณจะพบการสาธิตง่ายๆ

ห้องสมุดอื่นๆ

  • การบีบอัดจำนวนเต็มอย่างรวดเร็วใน Go: https://github.com/ronanh/intcomp
  • อัลกอริธึม Bitpacking ที่รวดเร็ว: พอร์ตสนิมของ simdcomp 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: การใช้งานที่รวดเร็วสำหรับการบีบอัดจำนวนเต็ม varbyte 32 บิต/64 บิต https://github.com/cruppstahl/libvbyte
  • TurboPFor เป็นไลบรารี C ที่มีการเพิ่มประสิทธิภาพที่น่าสนใจมากมาย คุ้มค่าที่จะตรวจสอบ! (ใบอนุญาต GPL) https://github.com/powturbo/TurboPFor
  • Oroch เป็นไลบรารี C ++ ที่เสนอ API ที่ใช้งานได้ (ใบอนุญาต MIT) https://github.com/ademakov/Oroch

ภาษาโปรแกรมอื่นๆ

  • มีกระดาษห่อสำหรับจูเลีย
  • มีพอร์ตสนิม

อ้างอิง

  • Daniel Lemire, Nathan Kurz, Christoph Rupp, สตรีม VByte: การบีบอัดจำนวนเต็มแบบไบต์ที่เร็วขึ้น, จดหมายประมวลผลข้อมูล, จดหมายประมวลผลข้อมูล 130, กุมภาพันธ์ 2018, หน้า 1-6https://arxiv.org/abs/1709.08990
  • Jianguo Wang, Chunbin Lin, Yannis Papakonstantinou, Steven Swanson, การศึกษาเชิงทดลองของการบีบอัดบิตแมปกับการบีบอัดรายการแบบกลับด้าน, SIGMOD 2017 http://db.ucsd.edu/wp-content/uploads/2017/03/sidm338-wangA pdf
  • P. Damme, D. Habich, J. Hildebrandt, W. Lehner, อัลกอริทึมการบีบอัดข้อมูลแบบ Lightweight: An Experimental Survey (การทดลองและการวิเคราะห์), EDBT 2017 http://openproceedings.org/2017/conf/edbt/paper-146 pdf
  • P. Damme, D. Habich, J. Hildebrandt, W. Lehner, ข้อมูลเชิงลึกในการประเมินเปรียบเทียบของอัลกอริธึมการบีบอัดข้อมูล Lightweight, EDBT 2017 http://openproceedings.org/2017/conf/edbt/paper-414.pdf
  • Daniel Lemire, Leonid Boytsov, Nathan Kurz, การบีบอัด SIMD และจุดตัดของจำนวนเต็มเรียงลำดับ, การปฏิบัติและประสบการณ์ด้านซอฟต์แวร์ 46 (6) 2016 http://arxiv.org/abs/1401.6399
  • Daniel Lemire และ Leonid Boytsov, การถอดรหัสจำนวนเต็มนับพันล้านต่อวินาทีผ่านเวกเตอร์, การปฏิบัติและประสบการณ์ซอฟต์แวร์ 45 (1), 2015 http://arxiv.org/abs/1209.2137 http://onlinelibrary.wiley.com/doi/10.1002 /spe.2203/บทคัดย่อ
  • Jeff Plaisance, Nathan Kurz, Daniel Lemire, การถอดรหัส VByte แบบเวกเตอร์, การประชุมวิชาการระดับนานาชาติเกี่ยวกับอัลกอริทึมของเว็บ 2015, 2015 http://arxiv.org/abs/1503.07387
  • Wayne Xin Zhao, Xudong Zhang, Daniel Lemire, Dongdong Shan, Jian-Yun Nie, Hongfei Yan, Ji-Rong Wen, แนวทางทั่วไปที่ใช้ SIMD เพื่อเร่งอัลกอริทึมการบีบอัด, ธุรกรรม ACM บนระบบสารสนเทศ 33 (3), 2015 http //arxiv.org/abs/1502.01916
  • TD Wu เทคนิค Bitpacking สำหรับการจัดทำดัชนีจีโนม: I. ตารางแฮช อัลกอริทึมสำหรับอณูชีววิทยา 11 (5) 2016 http://almob.biomedcentral.com/articles/10.1186/s13015-016-0069-5
ขยาย
ข้อมูลเพิ่มเติม
แอปที่เกี่ยวข้อง
แนะนำสำหรับคุณ
ข้อมูลที่เกี่ยวข้อง ทั้งหมด