HotCold & JediHotCold

This assignment’s goal was to convert a poorly aligned node structure in an unordered double-linked list into a new data structure with better cache performance.

BloatedNode, the original structure, was 2408 bytes, and 8 byte aligned.

For HotCold, I split the structure into two parts:

1. HotNode (32 bytes, 8 byte aligned), which contained pointers to previous and next HotNodes, a key value, and a pointer to one ColdNode
2. ColdNode (2388 bytes, 4 byte aligned), which contained all the other node data

For JediHotCold, I split the structure into three parts:

1. JediHotNode (64 bytes, 8 byte aligned), which contained an array of 10 key values, pointers to previous and next JediHotNodes, and a pointer to one JediRedirectNode
2. JediRedirectNode (80 bytes, 8 byte aligned), which contained an array of pointers to 10 JediColdNodes
3. JediColdNode (2388 bytes, 4 byte aligned), which contained all the other node data

To create both the HotCold and JediHotCold structures, the BloatedNodes were first iterated through to gain a precise count of the number of nodes. Then, I allocated each new split node type as separate array for superior spatial locality. When coupled with the increased temporal locality from a smaller node object, the search speed using the new structure paradigm vastly outperformed the original. The Jedi structure, in particular, demonstrated dramatic improvement.

Test Results

—————— HotCold Problem ——————
Bloated List create: 2.216183 s
HotCold convert: 173.138602 ms
Bloated find: 4.117100 ms
HotCold find: 0.575400 ms
Ratio: 7.155196

—————— JEDI Problem ——————
Jedi Bloated List create: 2.198650 s
Jedi HotCold convert: 189.181302 ms
Jedi Bloated find: 4.081000 ms
Jedi HotCold find: 0.105300 ms
Jedi Ratio: 38.755935