Home
Books
Virtual Creations
Physical Creations
About Me
Goats
Meta
Contact

Blogroll

Mon, Jan 1, 0001

+++ Description = “Using clustering on character sequences” date = “2021-04-29” draft = true menu = “main” title = “Sequence clustering” toc = true type = “page” +++

Counting bits

If we wish to count the bits on a word which are set, it easy, we use the POPCNT instruction.

However sometimes we have a large set n bit strings, and we wish to know, for each of the n bits, the number of the strings in which the nth bit is set. This is more difficult.

fn increment_in_place(&bits: &b128, counters: &mut [u64; 128]) {
    for i in 0..128 {
        counters[i] += (((bits.0 >> i) & 1) == 1) as u64;
    }
}

counters[i] += T::from_u8(((bits.0 >> i) & 1) as u8);
version n counter shape real time time per string ns per bit
0 32 u32 [(); 32] 237.656918ms 0.237656918 0.0074267786875
0 32 u32 [[(); 32]; 1] 239.423165ms 0.239423165 0.00748197390625
0 64 u32 [[(); 32]; 2] 321.716896ms 3.21716896 0.050268265
0 128 u32 [[(); 32]; 4] 819.500143ms 8.19500143 0.064023448671875
0 256 u32 [[(); 32]; 8] 1.840709531s 18.40709531 0.0719027160546875
0 512 u32 [[(); 32]; 16] 386.554638ms 38.6554638 0.075498952734375
0 1024 u32 [[(); 32]; 32] 897.085618ms 89.7085618 0.0876060173828125
0 1024 u32 [[[(); 32]; 32]; 1] 898.124399ms 89.8124399 0.08770746083984375
0 2048 u32 [[[(); 32]; 32]; 2] 1.763591947s 176.3591947 0.08611288803710937
0 4096 u32 [[[(); 32]; 32]; 4] 340.880629ms 340.880629 0.08322280981445312
0 8192 u32 [[[(); 32]; 32]; 8] 696.245361ms 696.245361 0.08499088879394531
0 16384 u32 [[[(); 32]; 32]; 16] 145.057799ms 1450.57799 0.08853625427246094
0 32768 u32 [[[(); 32]; 32]; 32] 288.768037ms 2887.68037 0.08812501129150391
version n counter shape real time time per string ns per bit
0 32 u8 [(); 32] 240.957944ms 0.240957944 0.00752993575
0 32 u16 [(); 32] 239.456283ms 0.239456283 0.00748300884375
0 32 u32 [(); 32] 238.024283ms 0.238024283 0.00743825884375
0 32 u64 [(); 32] 239.76403ms 0.23976403 0.0074926259375
0 1024 u8 [[(); 32]; 32] 942.328967ms 94.2328967 0.09202431318359375
0 1024 u16 [[(); 32]; 32] 941.50521ms 94.150521 0.0919438681640625
0 1024 u32 [[(); 32]; 32] 853.716706ms 85.3716706 0.0833707720703125
0 1024 u64 [[(); 32]; 32] 2.122190022s 212.2190022 0.2072451193359375
0 32768 u8 [[[(); 32]; 32]; 32] 290.186784ms 2901.86784 0.088557978515625
0 32768 u16 [[[(); 32]; 32]; 32] 275.44159ms 2754.4159 0.08405810241699219
0 32768 u32 [[[(); 32]; 32]; 32] 290.192835ms 2901.92835 0.08855982513427735
0 32768 u64 [[[(); 32]; 32]; 32] 662.750687ms 6627.50687 0.20225545867919922
version n counter shape real time time per string ns per bit st ns per bit mt per core
0 32 u8 [[(); 32]; 1] 389.327707ms 2.9007174596190453 0.09064742061309516 0.021455228561535478 0.34328365698456764
0 32 u16 [[(); 32]; 1] 294.686548ms 2.1955858767032623 0.06861205864697695 0.010150272399187088 0.1624043583869934
0 32 u32 [[(); 32]; 1] 418.423683ms 3.1174993738532066 0.09742185543291271 0.02229905966669321 0.35678495466709137
0 32 u64 [[(); 32]; 1] 853.38ms 6.3581764698028564 0.19869301468133926 0.022825009189546108 0.36520014703273773
version n counter shape real time time per string ns per bit st ns per bit mt per core
0 32768 u32 [[[(); 32]; 32]; 32] 1.313656207s 10022.401481628418 0.305859420215711 0.035140047082677484 0.5622407533228397
0 16384 u32 [[[(); 32]; 32]; 16] 1.315303682s 5017.4853591918945 0.30624300288036466 0.03367889788933098 0.5388623662292957
0 8192 u32 [[[(); 32]; 32]; 8] 1.332786302s 2542.0881309509277 0.31031349254772067 0.04881951422430575 0.781112227588892
0 4096 u32 [[[(); 32]; 32]; 4] 1.320834064s 1259.645523071289 0.30753064528107643 0.02962701302021742 0.4740322083234787
0 2048 u32 [[[(); 32]; 32]; 2] 1.305406664s 622.4664039611816 0.3039386738091707 0.0474867089651525 0.75978734344244
0 1024 u32 [[(); 32]; 32] 1.322553523s 315.32133173942566 0.30793098802678287 0.06135121895931661 0.9816195033490658
0 512 u32 [[(); 32]; 16] 1.323524376s 157.77640056610107 0.30815703235566616 0.06909680226817727 1.1055488362908363
0 256 u32 [[(); 32]; 8] 1.382187338s 82.38478529453278 0.32181556755676866 0.06354457489214838 1.016713198274374
0 128 u32 [[(); 32]; 4] 1.472638047s 43.88803383708 0.3428752643521875 0.08054430480115116 1.2887088768184185
0 64 u32 [[(); 32]; 2] 993.071556ms 14.79791933298111 0.23121748957782984 0.04206988820806146 0.6731182113289833
0 32 u32 [[(); 32]; 1] 423.588909ms 3.155983306467533 0.09862447832711041 0.022103375755250454 0.35365401208400726
0 32 u16 [[(); 32]; 1] 299.157084ms 2.228893965482712 0.06965293642133474 0.017162733944132924 0.2746037431061268
0 32 u64 [[(); 32]; 1] 854.593718ms 6.367219373583794 0.19897560542449355 0.029667478054761887 0.4746796488761902
0 32 u8 [[(); 32]; 1] 389.572245ms 2.902539409697056 0.090704356553033 0.021147557767108083 0.3383609242737293