Mirror of forum.nim-lang.org

1033 :: CritBitsTree vs Table

• axben (orginal) [2015-03-16T10:29:51+01:00] view original

  Right now, using Tables, you have to implicitly initialize any Table like so:

  import tables
  
  var T_base: array[0..1, Table[string, char]]
  
  T_base[0] = initTable[string, char]()  # Init
  T_base[0]["x"] = 'a'
  echo T_base[0]["x"]
  Run

  Running this code w/o the initialization in line 5 will result in a Traceback ("Attempt to read from nil?"). Is that really necessary? Why not add a check for nil (possibly - and most desirably initializing the Table dynamically)? That this is possible is shown in the CritBits module, using which, the following code runs w/o any problem:

  import critbits
  
  var
     C_base: array[0..1, CritBitTree[char]]
  
  C_base[0]["x"] = 'a'
  echo C_base[0]["x"]
  Run

  Also, coming back to the Tables code, please mind the double specification of T_base's generic types in initTable() (shouldn't that be known already?).

---

• jboy (orginal) [2015-03-16T14:33:30+01:00] view original

  To address your last question first, where is the "double specification" of T_base's generic type parameters? initTable() needs the generic types specified so that it can create & return a new table instance. The return value of initTable() is unrelated to the type of T_base or T_base[0] -- it just happens that the return value of initTable() is then assigned to T_base[0].

---

• jboy (orginal) [2015-03-16T14:57:31+01:00] view original

  Regarding your first question, I just had a look through the code of the tables & critbits modules (lib/pure/collections/tables.nim & lib/pure/collections/critbits.nim in the Nim source).

  On a purely technical level, the difference exists (ie, you need to initialize a Table[A, B] instance explicitly, but you don't need to initialize a CritBitTree[T] instance explicitly) because:

  • In Nim, the default object field initialization is nil-initialization.
  • CritBitTree[T] is a tree of nodes; the CritBitTree[T] type consists of a Node[T] and a count: int. The count will be nil-initialized to zero, while the Node[T], which is a typedef for ref NodeObj[T] will be nil-initialized to a nil-reference. Thus, a nil-initialized CritBitTree[T] instance is in a completely valid state.
  • In contrast, a Table[A, B] instance contains a KeyValuePairSeq[A, B] instance, which is a typedef for seq[KeyValuePair[A, B]]. As is noted in the Nim manual, the default nil-initialization of seq[T] instances leaves them in an invalid state. Hence, you need to invoke initTable(), which initializes the seq[T] instance using a call to newSeq.

  On a theoretical (data structures) level, it also makes sense:

  • CritBitTree[T] is a tree; and trees grow incrementally, node-by-node; and when your tree is created, it is empty, with no nodes in it.
  • In contrast, Table[A, B] is built around a seq[T] of an effective choice of initial length. The theoretical reason that you are asked to initialize the Table is so that you can specify a good initial-length value. The only reason you can invoke initTable() without specifying a length value is because it has a default initial length of 64.

  That said, I know that @Araq is not absolutely against the idea of enhancing seq[T] to auto-initialize in some cases, to avoid the runtime crashes that result from attempting to read from nil. I know this because I recently asked about that exact issue.

  So, perhaps you could create a PR on Github, suggesting that a similar allowance be made for Table[A, B]. You could suggest that if some code attempts to index into an uninitialized Table instance, the table will first be default-initialized to the initial-length of 64.

  I would suggest you open a PR.

---

• OderWat (orginal) [2015-03-16T23:25:37+01:00] view original

  I just want to stop by to say that a "PR" refers to a "Pull Request" which actually should present code that fixes the problem. I think it is meant to create an Issue on GitHub.

---

• jboy (orginal) [2015-03-17T00:41:37+01:00] view original

  Ha, you're right, @OderWat. Last week I knew that "PR" == "Pull Request", but for some reason yesterday, my brain decided that "PR" == "Problem Report". ;)

  (Ah well, time for me to create some pull requests.)

---