[Format] In-memory format for 128-bit Decimals, handling of sign bit

[asfimport]

cc @cpcloud

We found in ARROW-655 that we needed to add an extra bit for signedness for decimals stored as 128-bit values to be able to use the Boost multiprecision libraries. This makes Decimal128 not fit completely neatly as a 16-byte fixed size binary value, and more of a struct<sign_bitmap: boolean, data: fixed_size_binary(16)>. What is the current formata in the Java implementation? We will need to document the memory layout for decimals that maximizes compatibility across languages and eventually implement integration tests for IPC.

Reporter: Wes McKinney / @wesm
Assignee: Phillip Cloud / @cpcloud

Related issues:

• Integration tests for Decimal types (blocks)
• Add decimal type support to ArrowWriter. (is related to)

_{Note: This issue was originally created as ARROW-786. Please see the migration documentation for further details.}

[asfimport]

Jacques Nadeau / @jacques-n:
The current format of the java implementation is an embedded sign bit. GCC/Clang/Intel support __int128 which I believe on x86-64 machines is represented with the sign bit embedded ( ? ). I remember talking to @nongli about this years ago and (if I recall correctly), we chose the Parquet representation based on his experiments with GCC or Clang/LLVM. (Unfortunately, I'm unable to find the thread.)

The current Java implementation supports a 16-bit wide, sign-bit embedded twos-complement big-endian representation that is the same as the Parquet description here:

https://github.com/apache/parquet-format/blob/master/src/main/thrift/parquet.thrift#L81

[asfimport]

Jacques Nadeau / @jacques-n:
Would also be good to confirm the memory representation of <16 x i128> vector using llvm on x86-64.

[asfimport]

Phillip Cloud / @cpcloud:
@jacques-n __int128_t doesn't work on Windows (with visual cpp) and when I originally wrote the decimal code for arrow-cpp, it was buggy with clang. The symbols required to link in libc++ code necessary to use that type were not exported by clang. See here: https://bugs.llvm.org//show_bug.cgi?id=26156.

We ultimately went with the boost multiprecision representation (which is sign magnitude) because of desire to reuse existing libraries and cross platform capabilities out of the box.

One possible alternative (depending on whether clang issues have been resolved) is to write our own pared down of version of something like boost multiprecision that uses __int128_t on UNIXes and two int64_t s on Windows. It wouldn't need to have any operations at the moment, just the ability to print itself like a decimal number and convert decimal strings to the underlying type. Even those may be able to be functions and not methods on the class.

[asfimport]

Wes McKinney / @wesm:
@cpcloud is it possible to do bit twiddling to convert between the 16-byte Java/Parquet-compatible representation and the Boost::Multiprecision representation?

[asfimport]

Phillip Cloud / @cpcloud:
That should be possible.

Though because boost is using 128 bits + a sign bit, going from arrow-cpp to Java won't be possible in every case since the boost representation's values range from +/-0..2 ** 128 - 1, whereas the Java implementation's values range from -2 ** 127..2 ** 127 - 1.

The more I think about this and reread the boost multiprecision docs, I think we should just implement our own very small wrapper around native types.

Boost multiprecision has some optimizations that arrow doesn't care about like this that increase implementation complexity at best and hurt performance at worst:

When used at fixed precision, the size of this type is always one machine word larger than you would expect for an N-bit integer: the extra word stores both the sign, and how many machine words in the integer are actually in use.

plus the complexities of have two signed integer representations are enough to make me want to try jettisoning boost multiprecision.

[asfimport]

Wes McKinney / @wesm:
It seems like we might end up having to build a from-scratch implementation of Java's BigDecimal in C++. It might be worth it, but it's also a lot of work. The JDK source code is not ASF-friendly so we would have to start from scratch from a mathematical resource

[asfimport]

Wes McKinney / @wesm:
It doesn't look like this will be resolved in 0.6.0; moving to the next release

[asfimport]

Phillip Cloud / @cpcloud:
I'm going to try to start working on this this weekend. This should be up for the next release.

[asfimport]

Wes McKinney / @wesm:
OK, sweet, that would be awesome.

[asfimport]

Wes McKinney / @wesm:
Issue resolved by pull request 981
#981