I'm using the same codec as in the basic example. I can encode one array, but with my other array, I get this exception:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException
    at java.lang.System.arraycopy(Native Method)
    at integercompression.IntegratedBitPacking.integratedpack32(IntegratedBitPacking.java:4694)
    at integercompression.IntegratedBitPacking.integratedpack(IntegratedBitPacking.java:4915)
    at integercompression.IntegratedBinaryPacking.compress(IntegratedBinaryPacking.java:24)
    at integercompression.IntegratedComposition.compress(IntegratedComposition.java:20)

I have implemented DeltaZigzagBinaryPacking as an experiment. Zigzag encoding is from protocol buffer.

It has good (=small) "bit per int" for some kind of input sequences: sensors ouput or so. But It is bit slower than other BinaryPacking codecs, becaue of I didn't optimize it.

Benchmark's partial result is here:

| Dataset | CODEC | Bits per int | Compress speed (MiS) | Decompress speed (MiS) | | --- | --- | --- | --- | --- | | Sorted (mean=1048576 range=1024) | JustCopy | 32.00 | 2449 | 8921 | | Sorted (mean=1048576 range=1024) | BinaryPacking | 20.79 | 975 | 1458 | | Sorted (mean=1048576 range=1024) | DeltaZigzagBinaryPacking | 4.07 | 513 | 693 | | Sorted (mean=1048576 range=1024) | IntegratedBinaryPacking | 3.07 | 585 | 1233 | | Sorted (mean=1048576 range=1024) | XorBinaryPacking | 7.34 | 454 | 785 | | Sorted (mean=1048576 range=1024) | FastPFOR | 20.78 | 322 | 1185 | | Random (mean=1048576 range=1024) | JustCopy | 32.00 | 2498 | 8677 | | Random (mean=1048576 range=1024) | BinaryPacking | 21.28 | 981 | 1439 | | Random (mean=1048576 range=1024) | DeltaZigzagBinaryPacking | 11.54 | 515 | 667 | | Random (mean=1048576 range=1024) | IntegratedBinaryPacking | 32.28 | 940 | 2695 | | Random (mean=1048576 range=1024) | XorBinaryPacking | 21.28 | 443 | 817 | | Random (mean=1048576 range=1024) | FastPFOR | 21.23 | 356 | 1218 | | Sine (mean=1048576 range=1024 freq=1024) | JustCopy | 32.00 | 3574 | 9049 | | Sine (mean=1048576 range=1024 freq=1024) | BinaryPacking | 20.88 | 968 | 1308 | | Sine (mean=1048576 range=1024 freq=1024) | DeltaZigzagBinaryPacking | 6.24 | 544 | 638 | | Sine (mean=1048576 range=1024 freq=1024) | IntegratedBinaryPacking | 21.28 | 777 | 1608 | | Sine (mean=1048576 range=1024 freq=1024) | XorBinaryPacking | 12.20 | 455 | 734 | | Sine (mean=1048576 range=1024 freq=1024) | FastPFOR | 21.11 | 332 | 1101 | | Sine (mean=1048576 range=64 freq=64) | JustCopy | 32.00 | 2318 | 8507 | | Sine (mean=1048576 range=64 freq=64) | BinaryPacking | 20.88 | 928 | 1296 | | Sine (mean=1048576 range=64 freq=64) | DeltaZigzagBinaryPacking | 2.82 | 498 | 709 | | Sine (mean=1048576 range=64 freq=64) | IntegratedBinaryPacking | 19.38 | 747 | 1706 | | Sine (mean=1048576 range=64 freq=64) | XorBinaryPacking | 9.08 | 446 | 781 | | Sine (mean=1048576 range=64 freq=64) | FastPFOR | 21.11 | 331 | 1114 |

@lemire How do you think about this DeltaZigzagBinaryPacking? Does it seem to merge into master?

I changed the start of varyingLengthTest in BasicTest to:

            int N = 128;
            int[] data = new int[N];
            data[127] = -1;

Then the test fails. Should this work?

When I try out the unsortedExample I get an out of bound exception in getBestBFromData. This can be resolved by increasing the freqs array length to 33. But after decompressing the result is not the same as the input. Issue can be reproduced by adding after the initialization of the data array in the unsortedExample method from example.java:

data[5] = -311;

This is a minor refactoring of all codecs that directly allocate Java ByteBuffers: instead of making a direct call to ByteBuffer#allocate(), the codec invokes a protected method makeBuffer(size). This allows a user to subclass the codec and override the method to customize the buffer allocation.

In particular, this enables users to use heap-buffers and/or buffer pooling. The latter is essential for reducing memory churn.

In a JVM benchmark (not included) on some real-world data, this refactoring did not decrease performance. (Notice that dropping final from some classes does not stop the JVM from inlining, such as in monomorphic callsites.)

Hi

Great work. I been playing with this lately and when i tried to random access the compressed values (using the SkippableComposition) its throwing up ArrayIndexOutOfBounds Exceptions.

This approach works fine: codec.headlessUncompress(compressed,inPoso, uncompressed.length, output, outPoso, i)

But when i tried to change the inPoso to read from a particular index, it throws up exception.

Eg: inPoso.set(i) codec.headlessUncompress(compressed,inPoso, uncompressed.length, output, outPoso, 1)

Am i doing something wrong here? Or is it like we cannot uncompress a particular element? Any help would be appreciated.

I believe There is mistake in setting the size of the recovered int[] to ChunkSize in the advancedExample() method in https://github.com/lemire/JavaFastPFOR/blob/master/example.java,

int TotalSize = 2342351; // some arbitrary number
int ChunkSize = 16384; // size of each chunk, choose a multiple of 128

int[] data = new int[TotalSize];

int[] recovered = new int[ChunkSize];

If I do the following at the end:

        if(Arrays.equals(data, recovered)) {
            System.out.println("Elevation data is recovered in memory without loss");
        }
        else
            throw new RuntimeException("bug"); // could use assert

It would throw me the RuntimeException, since the data array and the recovered array are different and NOT of the same size.

https://github.com/lemire/JavaFastPFOR/blob/1d650e40f6ce3052042871161488971052c9fd32/example.java#L240-L243

• Note that this does not use differential coding: if you are working on sorted
  • lists, you must compute the deltas separately. //From file OptPFD.java

Doing so increases the size of the output array from 58 to 104 integers.

    new IntegratedComposition(new IntegratedBinaryPacking(),
      new IntegratedVariableByte()),
    new JustCopy(),
    new VariableByte(),
    new IntegratedVariableByte(),
    new Composition(new BinaryPacking(), new VariableByte()),
    new Composition(new NewPFD(), new VariableByte()),
    new Composition(new NewPFDS16(), new VariableByte()),
    new Composition(new OptPFD(), new VariableByte()),
    new Composition(new OptPFDS9(), new VariableByte()),
    new Composition(new OptPFDS16(), new VariableByte()),
    new Composition(new FastPFOR128(), new VariableByte()),
    new Composition(new FastPFOR(), new VariableByte()),
    new Simple9(),
    new Simple16(),
    new Composition(new XorBinaryPacking(), new VariableByte()),
    new Composition(new DeltaZigzagBinaryPacking(),
      new DeltaZigzagVariableByte()))

  def test2() = {
    val N = 100
    val r = new Random(System.nanoTime())
    val keys = (1 to N).map(i => {
      //r.nextInt(Int.MaxValue)
      i_Short.MaxValue_2+r.nextInt(Short.MaxValue*2)
    }).toArray
    println(keys.toList)
    println(s"size before compression ${keys.size}")
    codecs.foreach(codec => {
      print(s"${codec.toString} , ")
      val iic = new IntegratedIntCompressor()
      var start = System.nanoTime()
      val keys2 =  diffEncoder.compress(keys)
      val compressed = iic.compress(keys2) // compressed array
      val encodeTime = System.nanoTime() - start
      print(s" $encodeTime , ")
      print(s" ${compressed.size} , ")
      start = System.nanoTime()
      val recov = iic.uncompress(compressed)
      //val reKeys = diffEncoder.decompress(recov)
      val decodeTime = System.nanoTime() - start
      println(s" $decodeTime , ")
      //println("reKeys == keys  "+(reKeys.toList==keys.toList))
      //println("reKeys == keys  "+(reKeys==keys))

//println(compressed.toList) }) }

  object diffEncoder{
    def compress(in:Array[Int]):Array[Int]={
      val in1 = new Array[Int](in.length)
      var i = 0
      while(i < in.length){
        if(i == 0)
          in1(i) = in(i)
        else {
          in1(i) = in(i) - in(i-1)
        }
        i +=1
      }
      return in1
    }

def decompress(in:Array[Int]):Array[Int]={ val in1 = new ArrayInt var i = 0 while(i < in.length){ if(i == 0) in1(i) = in(i) else { in1(i) = in(i) + in1(i-1) } i +=1 } return in1 }

  }```

I encountered the same issue as #29 , except that I was using Integrated Composition instead of just Composition. To reproduce the error, consider the following code:

int x = 0;
SkippableIntegratedIntegerCODEC sortedCodec = new SkippableIntegratedComposition(
        new IntegratedBinaryPacking(), new IntegratedVariableByte());

int[] original = new int[] {1};
int[] compressed = new int[10];
IntWrapper outputOffset = new IntWrapper(x);
sortedCodec.headlessCompress(original, new IntWrapper(0), original.length, compressed, outputOffset, new IntWrapper(0));
System.out.println(Arrays.toString(compressed));

The output is [0, 129, 0, 0, 0, 0, 0, 0, 0, 0], meaning that [0] has been compressed into [0, 129]. However, if we change the first line to x = 1, the output is still [0, 129, 0, 0, 0, 0, 0, 0, 0, 0], meaning that this time [0] has been compressed into [129] instead.

A quick hack to fix the issue would be to switch the order of the two arguments being passed into SkippableIntegratedComposition(), but further experiments suggested that this would decrease performance.

Would you mind looking into this issue? Thanks!

Hi!

Composition does not generalise to cases where the input of the output array is not zero. To illustrate this, the following function prints "false" for x > 0, but not for x == 0.

public void test(int x) {
        int[] a = {2, 3, 4, 5};
        int[] b = new int[90];
        int[] c = new int[a.length];

        IntegerCODEC codec = new Composition(new BinaryPacking(), new VariableByte());

        IntWrapper aOffset = new IntWrapper(0);
        IntWrapper bOffset = new IntWrapper(x);
        codec.compress(a, aOffset, a.length, b, bOffset);
        int len = bOffset.get() - x;

        bOffset.set(x);
        IntWrapper cOffset = new IntWrapper(0);
        codec.uncompress(b, bOffset, len, c, cOffset);

        System.out.println(Arrays.equals(a, c));
}

A solution to this would simply consist in the following modification of the compress method:

    @Override
    public void compress(int[] in, IntWrapper inpos, int inlength,
            int[] out, IntWrapper outpos) {
        if (inlength == 0) {
            return;
        }
        int inposInit = inpos.get();
        int outposInit = outpos.get();
        F1.compress(in, inpos, inlength, out, outpos);
        if (outpos.get() == outposInit) {
            out[outposInit] = 0;
            outpos.increment();
        }
        inlength -= inpos.get() - inposInit;
        F2.compress(in, inpos, inlength, out, outpos);
    }

Cheers

Hi, I'm new to java and this library in general. I want to save the compressed int[] to redis. The only way to do this is to first convert the int[] to a byte[]. Is there any way to get a byte[] array from the compressed int[] short of using ByteBuffer. Thanks, Rr.

Hi lemire/JavaFastPFOR!

This is a one-off automatically generated pull request from LGTM.com :robot:. You might have heard that we’ve integrated LGTM’s underlying CodeQL analysis engine natively into GitHub. The result is GitHub code scanning!

With LGTM fully integrated into code scanning, we are focused on improving CodeQL within the native GitHub code scanning experience. In order to take advantage of current and future improvements to our analysis capabilities, we suggest you enable code scanning on your repository. Please take a look at our blog post for more information.

This pull request enables code scanning by adding an auto-generated codeql.yml workflow file for GitHub Actions to your repository — take a look! We tested it before opening this pull request, so all should be working :heavy_check_mark:. In fact, you might already have seen some alerts appear on this pull request!

Where needed and if possible, we’ve adjusted the configuration to the needs of your particular repository. But of course, you should feel free to tweak it further! Check this page for detailed documentation.

Questions? Check out the FAQ below!

FAQ

JDK 16 introduces the Vector API for SIMD parallelism directly from Java code: https://docs.oracle.com/en/java/javase/16/docs/api/jdk.incubator.vector/jdk/incubator/vector/package-summary.html

My understanding is that since the original FastPFOR library takes advantage of SIMD, it should be possible to make this one as well. Is that correct?

Hi,

I'm interested in decoding integers from an off-heap direct buffer, but I currently see no way of doing this without copying them to the heap. Is there a suggested method of doing this? Is there a fundamental (eg. performance) reason why this is not implemented or is it just to avoid the complexity?

Thanks, Viktor

Assume I have 10,000 int, which range from -9000 to +21000 in value.

What would be the strategy of writing the int[] already compressed by JavaFastPFOR into a file for archive ?

Should I assume I need to convert each int into 4 bytes ?

So will an int[] array with 10,000 values will be saved as a byte[] array with the size of 40,000 ?

Any other more optimal way to save the data into a file ?

I am experimenting with this library and the project panama vector API. In my fork, I have restructured the project slightly to make it easier to run benchmarks on a branch. The changes are all related to moving code around and bumping the Java language level. Would these changes be useful? If so, how could it be validated that they don't break your release process?