Choosing the Right Nim Table: CountTable vs OrderedTable for Reproducible Word Counts

Problem: Reproducible Word Counting in Nim

When parsing text, developers often need a quick way to tally how many times each word appears. In Nim, the standard library offers a CountTable for this exact purpose. However, many projects also need to output the results in a deterministic order—either the order words were first seen or a sorted order. The default Table type does not guarantee any order, while OrderedTable preserves insertion order but incurs extra cost. This blog explores those trade‑offs and shows a concrete example that helps you decide which to use.

Understanding Nim’s Table Types

The std/tables module provides three related containers:

• Table[Key, Value] – a plain hash table. Keys are stored in a hash bucket array; iteration order is undefined.
• OrderedTable[Key, Value] – a hash table that also keeps a linked list of keys in the order they were inserted.
• CountTable – a convenience wrapper around Table[string, int] with an inc procedure for incrementing counts.

All three types have value semantics: passing a table to a proc copies it unless the parameter is declared var or you use a reference type like TableRef.

When Order Matters

Iteration order is often important when you need reproducible output, such as generating a report or feeding data into a deterministic algorithm. With Table, the order can change between compiler versions or even between runs on the same machine. In contrast, OrderedTable guarantees that iterating over the keys will return them in the exact sequence they were first inserted.

Because CountTable is built on Table, its iteration order is also unspecified. If you require order, you must either sort the keys after counting or use OrderedTable directly.

Concrete Example: Word Frequency Counter

Below is a minimal Nim script that counts word frequencies in a paragraph and prints them sorted alphabetically. It demonstrates how to use CountTable and how to switch to OrderedTable if you want insertion order.

import std/[strutils, tables, sequtils]

# Sample text
let text = "Nim is fast, Nim is expressive, and Nim is fun"

# 1. Using CountTable (unordered)
var freq = initCountTable[string]()
for word in text.split(" "):
  freq.inc(word)

echo "[CountTable] Unordered output:"
for k, v in freq.pairs:
  echo "  " & k & ": " & v

# 2. Using OrderedTable for deterministic order
var ordered = initOrderedTable[string, int]()
for word in text.split(" "):
  ordered.inc(word)

echo "[OrderedTable] Insertion order output:"
for k, v in ordered.pairs:
  echo "  " & k & ": " & v

# 3. Sorted output from CountTable
let sortedKeys = freq.keys.sorted()
echo "[CountTable] Sorted output:"
for k in sortedKeys:
  echo "  " & k & ": " & freq[k]

Run the script with nim r wordcount.nim. The CountTable section will likely print words in an unpredictable order, whereas the OrderedTable section will preserve the order of first appearance. The sorted section demonstrates a quick way to get deterministic output without changing the table type.

Trade‑Offs & Limitations

Feature	Table	OrderedTable	CountTable
Memory Footprint	Lowest	~+30% (auxiliary list)	Same as Table
Lookup Speed	Fastest	slightly slower (list maintenance)	Fast (hash only)
Insertion Order	No	Yes	No
Specialized for Strings	No	No	Yes (string → int)
Thread Safety	No (value semantics)	No	No
Copy Cost	High for large tables	High	High (value semantics)

Key takeaways:

• Use CountTable for quick, unordered frequency counting when order is irrelevant.
• If you need the order of first appearance, switch to OrderedTable or sort the keys after counting.
• For large tables that need to be shared across procedures, consider passing a var or using TableRef to avoid costly copies.
• Both Table and OrderedTable are not thread‑safe; use locks or thread‑local tables for concurrent increments.

Actionable Guidance

1. Identify whether your use case cares about iteration order.
2. If order is irrelevant, CountTable gives the simplest API.
3. If order matters, prefer OrderedTable for insertion order or sort the keys when printing.
4. When performance is critical and you’re working with many keys, benchmark both types in your target environment; the overhead of OrderedTable is modest but measurable.

By making this decision early, you avoid subtle bugs caused by nondeterministic iteration and keep your code clean and efficient.