Do we have a shift operation for array elements in Nim like this one? Well, now we have.
The filling with default value: I am using a compiler initialized var to get the default. Is that the suggested way?
proc shift[T](a: var openarray[T]; d: int) =
## Shift a right by d places for positive d or
## left for negative d.
## Shifted in elements are filled with default value.
var
h: T
j: int
if d > 0: # right shift
j = a.high
while j >= d:
a[j] = a[j - d]
dec(j)
j = min(d, a.len)
for i in 0 ..< j:
a[i] = h
elif d < 0: # left shift
j = -d
while j < a.len:
a[j + d] = a[j]
inc(j)
j = max(a.len + d, 0)
for i in j .. a.high:
a[i] = h
var ta = [1,1,1]
shift(ta, 1)
assert(ta == [0,1,1])
ta = [1,1,1]
shift(ta, 2)
assert(ta == [0,0,1])
ta = [1,1,1]
shift(ta, 3)
assert(ta == [0,0,0])
ta = [1,1,1]
shift(ta, 4)
assert(ta == [0,0,0])
ta = [1,1,1]
shift(ta, -1)
assert(ta == [1,1,0])
ta = [1,1,1]
shift(ta, -2)
assert(ta == [1,0,0])
ta = [1,1,1]
shift(ta, -3)
assert(ta == [0,0,0])
ta = [1,1,1]
shift(ta, -4)
assert(ta == [0,0,0])
Nice, though I'm used to shift meaning "remove the first value of the (resizable) array and return the value", I think your proc feels more like it's "scrolling" the array?
Anyway, naming aside, what do you think of this version?
proc scroll[T](a: var openarray[T]; d: int) =
if d == 0: discard # do nothing
elif abs(d) >= a.len: # reset all
for el in a.mitems: el.reset
elif d > 0: # right shift
for i in countdown(a.len-1,d):
a[i]=a[i-d]
for j in 0..<d: a[j].reset
elif d < 0: # left shift
for i in -d..<a.len:
a[i+d]=a[i]
for j in countdown(-d,1): a[^j].reset
Yes, for some languages shift may mean returning an element. But in Nim we have shl and shr operators. scroll may be confused with rotation?
I will look at your code in more detail tonigth -- you are using magic reset proc from system module. I tried also a year ago, then I asked Araq in IRC about the comment "This needs to be called before any possible object branch transition." in the docs. He just told me I should not use it if I do not understand purpose, so I removed that proc from my code.
@OderWat
Sorry, can not really understand... Somethink like memCopy or memMove? That was my first idea, but I was very unsure what would happen when array elements are not somethink like plain ints, but objects with refs. Would that confuse the GC?
And of course one may ask if array shifting is a good idea at all -- for many use cases other data structures may be a better solution. I was in need for that shifting for may chess game -- there position in the array is bound to ply, use of array is very convenient and overhead is very low. I can not remember if i inspected Nim sources before i started coding the shift proc -- I think so, but coding time was some months ago. I guess for seqs there may exist a deleteAt() which we may inspect.
@OderWat: do you mean something like this?
proc shift[T](a: var openarray[T]; d: int) =
if d == 0: discard # do nothing
elif abs(d) >= a.len: # reset all
zeroMem(addr a[0], a.len*sizeof(T))
elif d > 0: # right shift
moveMem(addr a[d], addr a[0], (a.len - d)*sizeof(T))
zeroMem(addr a[0], d*sizeof(T))
elif d < 0: # left shift
moveMem(addr a[0], addr a[-d], (a.len + d)*sizeof(T))
zeroMem(addr a[^(-d)], -d*sizeof(T))
But as Stefan said, I'm not sure how the gc sees this ( I think it's fine, as the total amount of memory doesn't change ( right? ) , we just change its value )
ps: what's a good way to benchmark this ( on windows ) ?
Edit: thinking about it, I'm not sure what would happen to refs that get moved
I was thinking about refs too and I kinda doubt that just moving the refs in memory works. Sequtils usually uses shallowCopy() for manipulation of elements in the seq. Which imho avoids (deep) copying a string or seq inside the seq and copies the "pointer" (reference). I guess OP shift() proc does not work very well for strings and seq types as they will be copied when only using =.
Looking at delete() in sequtils one also sees that there is nothing obviously done to delete entries. But this is probably part of shallowCopy() and maybe also part of setLen(). I did not dig into it but looking at it makes me think that simple memory manipulation is not enough. I still wonder if it would be ok (and faster) with non ref types in the seq.
Maybe the code from @stisa does work without refs or even with refs... maybe needing the addition of something like shallowCopy() to move the second element into the first elements position before the memory move to "free" the former first element correctly. Maybe one needs to unref() it.. or that whole thought is stupid :)
I guess some people here know more about the internals and can answer if and when it works and if it partly would work, why it is not used in sequtils() for example.
It just feels "strange" that there is a solid memory block and then one does move element by element instead of doing what one would do in C...
If you are wanting to remove elements from the start of the seq and shift data elements to the front,
shouldn't you be using a queue rather than a sequence?
@jlp765 : yeah probably, and stefan said that, but I find this interesting :)
So, based on this thread , using reset on the elements we move out of the array should handle ref etc. properly.
The code becomes this:
proc shift[T](a: var openarray[T]; d: int) =
if d == 0: discard # do nothing
elif abs(d) >= a.len: # reset all
for el in a.mitems: el.reset
elif d > 0: # right shift
for j in 0..<d: a[j].reset # Reset only items that will be overwritten
moveMem(addr a[d], addr a[0], (a.len - d)*sizeof(T))
elif d < 0: # left shift
for j in countdown(-d,1): a[^j].reset # Reset only items that will be overwritten
moveMem(addr a[0], addr a[-d], (a.len + d)*sizeof(T))
And running a naive benchmark on a win10 notebook with a quadcore i7 I get:
CPU time: original 4.125s
Delta occupied mem: original -483328
CPU time: first stisa 4.712s
Delta occupied mem: first stisa -479232
CPU time: possibly leaking 0.04900000000000127s
Delta occupied mem: possibly leaking -475136
CPU time: last stisa 2.199999999999999s
Delta occupied mem: last stisa -479232
Note that last stisa gets closer to possibly leaking the closer to the edges we shift, while original and first stisa gets slower:
shift(1):
CPU time: original 23.974s
Delta occupied mem: original -483328
CPU time: first stisa 24.081s
Delta occupied mem: first stisa -479232
CPU time: possibly leaking 0.03900000000000148s
Delta occupied mem: possibly leaking -475136
CPU time: last stisa 0.03899999999999437s
Delta occupied mem: last stisa -479232
shift(5000):
CPU time: original 3.789s
Delta occupied mem: original -430080
CPU time: first stisa 4.361000000000001s
Delta occupied mem: first stisa -475136
CPU time: possibly leaking 0.05000000000000071s
Delta occupied mem: possibly leaking -479232
CPU time: last stisa 2.216999999999999s
Delta occupied mem: last stisa -479232
I don't understand the gc enough to draw any conclusions,and it may very well be that what I wrote is flawed in ways I can't see.
ps: compiling with -d:release brings down times considerably, eg shift(1) :original 2.5s ( last_stisa 0.035s) and shift(5000):original 0.8s ( last_stisa 0.38s)
pps: is there a way to know how many times something is referenced? ( so I can tell how many calls to GC_unref() would be needed to cause the gc to collect it )
I would like to throw in my implementation that is inspired by std::transform from c++.
proc genRangeswap[Coll](data: var Coll; s0, s1, N: Natural): void =
for i in 0 ..< N:
swap(data[s0+i], data[s1+i])
proc genTransform[Coll](data: var Coll; first, middle, last: Natural): void =
assert(0 <= first and first <= middle and middle < last and last <= data.len)
if first == middle:
return
let
N = middle - first
M = last - middle
if N < M:
genRangeswap(data, first , middle , N )
genTransform(data, first+N, middle+N, last)
else: # M >= N
genRangeswap(data, first , middle , M )
genTransform(data, first+M, middle, last)
proc transform*(data: var string; first, middle, last: Natural): void =
genTransform(data, first, middle, last)
proc transform*(data: var string; middle: Natural): void =
genTransform(data, 0, middle, data.len)
proc transform*[T](data: var openarray[T]; first, middle, last: Natural): void =
genTransform(data, first, middle, last)
proc transform*[T](data: var openarray[T]; middle: Natural): void =
genTransform(data, 0, middle, data.len)
It has a generic core implementation that is not exported, and has a few wrappers that are mostly there to prevent false positives in auto completion. Everything is based on the rangeswap function that basically swaps two subranges of the same sequence. It is implemented in a way that it could easily be optimized for some sort of memswap on the string type. I don't know yet how safe it is to use memory swapping on other types, but I have a positive feeling that it is possible even though it sounds pretty dangerous to do so.