learnkdb
Back to Lookup By Key

Dictionaries · Lookup By Key · Practice Question

Improving Lookup Performance in Large Dictionaries

Sign in to track your progress

Question

Large dictionaries are often used in trading systems to store reference data such as instrument metadata, exchange mappings, or symbol lookups.

How can lookup performance be improved when working with very large dictionaries? Demonstrate the performance improvement with an example.

Solution

When all dictionary keys are unique, applying the unique attribute (u#) to the key list allows q to build an internal hash table.

This enables hash-based lookups rather than a linear search through the key list, significantly improving lookup performance for large dictionaries.

N:10000000

Keys:neg[N]?N          / 10 million unique long keys
Values:N?100f

d1:Keys!Values
d2:(`u#Keys)!Values

list:1000?N            / random lookup keys

Now time 1,000 individual lookups against each dictionary with \ts (which reports milliseconds and bytes used):

q)\ts r1:d1 each list
2767 32768
q)\ts r2:d2 each list
0 32768
q)r1~r2
1b

Your timings will differ by machine, but the gap is typically several orders of magnitude.

Explanation

By default, dictionary lookups perform a search through the key vector. For small dictionaries this is typically very fast, but lookup times increase as the number of keys grows.

When the key vector has the unique attribute (u#), q can use an internal hash table to locate keys directly. This reduces the lookup cost from approximately O(n) to O(1), making lookups effectively constant time regardless of dictionary size.

This can provide substantial performance improvements when repeatedly querying large reference-data dictionaries, such as:

  • Instrument metadata
  • Symbol-to-exchange mappings
  • Currency conversion tables
  • Market data subscriptions
  • Security master data

In the example above, both dictionaries return identical results:

q)r1~r2
1b

However, the dictionary whose keys have the unique attribute performs the lookups dramatically faster.

Note: The unique attribute can only be applied when all keys are distinct. Attempting to apply u# to a list containing duplicate values will result in a 'u-fail error.