nimforum mirror - Sequences and heap

andrea (orginal) [2015-01-23T12:33:23+01:00] view original

Are seq always allocated on the heap and garbage collected?

Is it possible that when the compiler is able to determine the length, or prove that it is short enough anyway, sequences could be represented as stack-allocated C arrays or variable length arrays?

LeuGim (orginal) [2015-01-23T13:39:13+01:00] view original

when the compiler is able to determine the length

But the length for seqs is changeable at runtime. If you know max length you need in advance you just use static arrays, like array[0..9, int].

andrea (orginal) [2015-01-23T14:19:47+01:00] view original

Yes, I know, but often one has a bound on the length but knows the actual legth only at runtime. In those cases it can be inconvenient to work with an array that seems to have a certain number of elements, while keeping track that only the first part is actually meaningful. One has to pay attention not to use high or len or iterate over the elements and so on. I guess it would be feasible to make a data structure that wraps an array, providing more meaningful operations - I was just hoping that one such structure would be in the standard library

LeuGim (orginal) [2015-01-23T14:43:20+01:00] view original

Yes, it's exactly the way (an object with data: array and size: int), and I don't know of such a type in stdlib; it's easy implementable.

Araq (orginal) [2015-01-23T15:09:14+01:00] view original

Is it possible that when the compiler is able to determine the length, or prove that it is short enough anyway, sequences could be represented as stack-allocated C arrays or variable length arrays?

Yes and once the compiler gets the optimizer it deserves which includes escape analysis, it's simple to do. There is no need for yet another slightly different builtin type to get that feature.

andrea (orginal) [2015-01-23T15:37:06+01:00] view original

That would be wonderful! :-)

By the way, the following naive solution:

type VLA*[N: static[int], A] = object
  content: array[0 .. N - 1, A]
  length: int

proc newVLA*[N: static[int], A]: VLA[N, A] =
  VLA[N, A](content: array[0 .. N - 1, A], length: N)

proc low*[N: static[int], A](a: VLA[N, A]): int = 0

proc high*[N: static[int], A](a: VLA[N, A]): int = a.length

proc len*[N: static[int], A](a: VLA[N, A]): int = a.length

iterator items*[N: static[int], A](a: VLA[N, A]) =
  for i in 0 .. < a.length:
    yield a.content[i]

proc `[]`*[N: static[int], A](a: var VLA[N, A], key: int): A =
  if key < 0 or key > N: raise RangeError
  a.content[key]

proc `[]=`*[N: static[int], A](a: var VLA[N, A], key: int, val: int) =
  if key < 0 or key > N: raise RangeError
  a.content[key] = val
  if key >= a.length: a.length = key + 1

fails with Error: type expected when I do

let v = newVLA[15, int]()

or even

let v: VLA[15, int] = newVLA[15, int]()

def (orginal) [2015-01-23T15:52:47+01:00] view original

There was another thread about variable length arrays, with a nice solution by Jehan: http://forum.nim-lang.org/t/499

andrea (orginal) [2015-01-23T16:04:30+01:00] view original

Yes, I have seen it. I am trying to test both approaches - of course mine is much more expensive, and less flexible, but I am not sure I will be able to make Jehan approach safe. Any ideas why the above does not compile?

LeuGim (orginal) [2015-01-23T18:31:36+01:00] view original

this works:

var v: VLA[15, int]

And you should add new before RangeError.

Also there are issues reported, e.g. https://github.com/Araq/Nim/issues/1017.

And you cannot use the same with let, because then you need to provide value, and it's unchangeable, so there's no point (you can then use just an array, if it's not changed).

mapdog (orginal) [2015-01-23T20:22:03+01:00] view original

Could we have a seq type with a fill pointer?

It would allow you to have a newStringOfCap() equivalent for seq.

(make-array 1000 :fill-pointer 0)

proc newSeqF(size, fillPointer = 0)

Mirror of forum.nim-lang.org

784 :: Sequences and heap