Support for int128 and uint128

[shayanhabibi]

The topic of supporting big ints like int128 and uint128 come up frequently.

I'd like to know what the thoughts are with supporting these internally, or at least providing better support for using them on supported archs.

This is how it currently has to be used afaik if I want to take advantage of builtin operations like double word atomic ops on viable architectures:

type
  int128* {.importc: "__int128".} = object
    DONOTACCESS, DONOTACCESS2: uint64
    # Accessing any of these fields would get passed onto
    # C; this will therefore fail since the int128 type is
    # a base type.
    # Another issue raised is that there could potentially be
    # poor alignment in allocations which can cause undefined
    # behaviour in edge cases
  hint128* = object
    # Because of the problem above, we need to use a helper
    # object as a go between
    hi*, lo*: uint64

In the case of using double word atomics:

proc atomicAddFetch(p: ptr int128, v: int128, mo = ATOMIC_SEQ_CST): int128 {.cdecl:"__atomic_add_fetch".}

var start = hint128(hi: 0'u64, lo: 1'u64)
let adder = hint128(hi: 1'u64, lo: 0'u64)
let result = atomicAddFetch(cast[ptr int128](unsafeAddr start), adder)
assert cast[hint128](result) == hint128(hi: 1'u64, lo: 1'u64)

This feels very obstructive and reduces clarity of the codebase.

[saem]

Both those types look like they're trying to do the same thing, sorta. Could you elaborate on the example with some comments? Thanks.

[shayanhabibi]

I've edited the original, please do not hesitate to let me know if there is anything further I should elaborate on.
Thank you!

[shayanhabibi]

I'd further like to comment that double word atomic ops are essential for producing the most modern lock free data structures; there's no way to take advantage of this natively in nimskull at the moment that doesn't look like the example AFAIK

Obviously I'd be stupendously surprised and delighted if someone can point me in the direction of a better path to take.

[saem]

One option might be to, allow/improve the following:

• size pragma to support more than 8 bytes, 16 in this case
• align pragma support on the object type itself

Then the type could be defined in either std/system or some other module (possibly new).

[shayanhabibi]

Perhaps, in recognition of its more limited portability, we would have it as a pkg or require explicit import?

It certainly would benefit from both options. It would really lubricate things if there wasn't a requirement to 'hack' these types in a low level programming language

[starsiderfox]

Here's my attempt:

type
    int128* = object
        hi*{.align:16.}, lo*: uint64
    cint128 {.importc: "__int128",nodecl.} = object

proc atomicAddFetch(p: ptr cint128, v: cint128, mo = ATOMIC_SEQ_CST): cint128 {.importc:"__atomic_add_fetch",nodecl,discardable.}

proc `+`*(a,b: int128): int128 {.inline.} =
    result = a
    discard atomicAddFetch(cast[ptr cint128](result.addr), cast[ptr cint128](b.addr)[])

proc `+=`*(a: var int128, b: int128) {.inline.} =
    atomicAddFetch(cast[ptr cint128](a.addr), cast[ptr cint128](b.addr)[])


var start = int128(hi: 0'u64, lo: 1'u64)
let adder = int128(hi: 1'u64, lo: 0'u64)

echo start + adder
echo start
start += adder
echo start

Here the builtin __int128 is just used for casting without having to tell the compiler the size or anything. And the main type, int128, has the align on its first member to ensure alignment (otherwise it crashes when you use it e.g. inside an object where it's not aligned).

Hopefully the double casts of b would be optimized out by the compiler.

[shayanhabibi]

Align takes a number of bytes as a parameter. In this case you are aligning by 128 bytes rather than bits

I'm not sure, but I'd also be concerned about how the nim vm would interpret this, since internally it looks like cint is at most 8 bytes large (since only C knows otherwise)

[starsiderfox]

Edited to align by 128 bits not bytes.

[starsiderfox]

Edited again because it doesn't seem to work with an alignment of 16.

[shayanhabibi]

This is probably supportive of the problem and the importance of internal support

[starsiderfox]

Edited again to restore align:16 which works correctly after fixing += which needs a var.

I realized this while making this other implementation which is simpler (and possibly more efficient):

type int128* {.importc: "__int128",nodecl.} = object
    # these fields don't exist in C, so we should avoid reading them
    hi{.align:16.}, lo: uint64

proc newInt128*(value: array[2, uint64]): int128 {.inline.} =
    result = cast[int128](value)

proc `$`*(v: int128): string =
    $cast[array[2, uint64]](v)

proc atomicAddFetch(p: ptr int128, v: int128, mo = ATOMIC_SEQ_CST): int128 {.importc:"__atomic_add_fetch",nodecl,discardable.}

proc `+`*(a,b: int128): int128 {.inline.} =
    result = a
    discard atomicAddFetch(result.addr, b)

proc `+=`*(a: var int128, b: int128) {.inline.} =
    atomicAddFetch(a.addr, b)

var start = newInt128 [10'u64, 2'u64]
var adder = newInt128 [1'u64, 20'u64]

echo start + adder
echo (start, adder)
start += adder
echo (start, adder)