type
Units* = SomeUnsignedInt
BitVecS*[S:static int, B:Units = uint] = object
Base*: array[S div (sizeof(B) * 8) + int(S mod (sizeof(B) * 8) != 0), B] #8,16,32,64
BitVec*[B:Units] = object
Base: seq[B]
size: int
AnyBitVec[S:static int, B:Units] = (BitVecS[S, B] | BitVec[B])
proc `[]`*[S,B](bv:AnyBitVec[S, B], i:int): int =
return (bv.Base[i div (B.sizeof * 8)] shr (i and (B.sizeof * 8 - 1)) and 1).int
func newBitVector*[B](size: int, init = 0): BitVec[B] {.inline.} =
var blocks = size div (sizeof(B) * 8) + int(size mod (sizeof(B) * 8) != 0)
result.Base = newSeqOfCap[B](blocks)
result.Base.setlen(blocks)
result.size = size
var bv1: BitvecS[20240001]
var y = newBitVector[uint32](1000)
discard y[0] #this failsI am trying to write a bitvector lib that has a common implementation for static (array) and dynamic (seq) ones, with user defineable base unit of storage. For static one I need S (static size) and B (base unit), while for the dynamic one I only need B. I tried like in the code above, but when accessing any procs on the dynamic one (BitVec), I get "Error: cannot instantiate: 'S'". I thought this would work since BitVec doesn't have/need S, but no. I got around it by adding the S parameter to the type, and passing a random number as generic parameter when calling procs on it, and while this works, it's obviously not pretty, and makes me believe there has to be a way to make this work cleanly. I was told to use concepts, but I couldn't make that work either, and I really don't understand how they work even after reading the doc. But I'd like not to use them unless absolutely necessary. Also, on a side note, the default generic parameter type I have on BitVecS (B:Units = uint) seems to actually work, although I was told it shouldn't. Any idea why it works (in this context)?
type
Units* = SomeUnsignedInt
BitVecS*[S:static int, B:Units = uint] = object
Base*: array[S div (sizeof(B) * 8) + int(S mod (sizeof(B) * 8) != 0), B] #8,16,32,64
BitVec*[B:Units] = object
Base: seq[B]
size: int
AnyBitVec = BitVecS or BitVec
proc `[]`*(bv:AnyBitVec, i:int): int =
type B = bv.B
return (bv.Base[i div (B.sizeof * 8)] shr (i and (B.sizeof * 8 - 1)) and 1).int
func newBitVector*[B](size: int, init = 0): BitVec[B] {.inline.} =
var blocks = size div (sizeof(B) * 8) + int(size mod (sizeof(B) * 8) != 0)
result.Base = newSeqOfCap[B](blocks)
result.Base.setlen(blocks)
result.size = size
var y = newBitVector[uint32](1000)
echo y[0]Furthermore, every generic type automatically creates a type class of the same name that will match any instantiation of the generic type.
use openArray[T] then.
Also I want to have max performance, and one extra proc call is not ideal.
If your public proc is tagged inline there is no extra cost.
The tradeoffs are:
Furthermore all the procedures for bit vectors are very small so tagging all inline makes sense.
Lastly, a division or modulo operation takes about 55 cycles. An addition/shift/and instruction takes 1 cycle at most. Since everything you divide or modulo with is a power of 2 use shr log2(n) for division and and (n-1) for modulo.
As mentioned on Discord, use ceil_division for sizing your bitvector:
proc ceilDiv(a, b: int) =
(a+b-1) div b
You can adapt it to b being a power of 2
this compiles but I get SIGSEGV on executing
It's strange, in my experience it's the nim compiler itself that SIGSEGV
Anyway, it's a bug and should be reported in the tracker.
You are right mratsim, it's the nim compiler that sigsegv.. which is obviously a bug, no doubt about it :) I will report it.
Speaking of bugs and types, I almost forgot this little code snippet when I was trying to figure out concepts: https://play.nim-lang.org/#ix=4wl7
Code behaves correctly but for some reason the [] proc is very slow. I get ~45 second runtime vs ~4ms what it normally should be, for 4 million operations. 10.000x slower. While the []= proc is as fast as it's supposed to be.
I lack the skills to figure out the root cause of this, maybe you or someone else with some time can try and see if this is a nim bug, or there is something wrong with my code in this context. But it looks like a bug. Using nim-devel.
Code behaves correctly but for some reason the [] proc is very slow. I get ~45 second runtime vs ~4ms what it normally should be, for 4 million operations. 10.000x slower. While the []= proc is as fast as it's supposed to be.
The code compiles to
typedef NU8 tyArray__3Ihb9ak9b9bUiqPPTJrVEaTqQ[500001];
struct tyObject_BitVecS__46rKYwOEk3TCNKA4N4J2aQ {
tyArray__3Ihb9ak9b9bUiqPPTJrVEaTqQ Base;
};
N_LIB_PRIVATE N_NIMCALL(void, X5BX5Deq___test95bitv_123)(tyObject_BitVecS__46rKYwOEk3TCNKA4N4J2aQ* bv, NI i, NI value) {
NU8* w;
w = (&(*bv).Base[((NI)(i / ((NI) 8)))- 0]);
{
if (!(value == ((NI) 0))) goto LA3_;
(*w) = (NU8)((*w) & (NU8)((NU8) ~((NU8)((NU64)(((NU8) 1)) << (NU64)((NI)(i & ((NI) 7)))))));
}
goto LA1_;
LA3_: ;
{
(*w) = (NU8)((*w) | (NU8)((NU64)(((NU8) 1)) << (NU64)((NI)(i & ((NI) 7)))));
}
LA1_: ;
}
N_LIB_PRIVATE N_NIMCALL(NI, X5BX5D___test95bitv_201)(tyObject_BitVecS__46rKYwOEk3TCNKA4N4J2aQ bv, NI i) {
NI result;
result = (NI)0;
result = ((NI) ((NU8)((NU8)((NU8)(bv.Base[((NI)(i / ((NI) 8)))- 0]) >> (NU64)((NI)(i & ((NI) 7)))) & ((NU8) 1))));
return result;
}
So tyObject_BitVecS__46rKYwOEk3TCNKA4N4J2aQ a 500kB object is copied by value on each access X5BX5D___test95bitv_201 but it's passed by pointer for mutation in X5BX5Deq___test95bitv_123
It's a codegen bug, however I already raised a similar one here https://github.com/nim-lang/Nim/issues/16897 which was supposed to be fixed.
Anyway you can raise the bug.