PA2 - Keep the hot side hot and the cold side cold

What up dudes!

Long hiatus, I know, sorry about that! But here I am again, this time I will explain Assignment #2 (PA2) – The Hot/Cold data structure.

This Hot/Cold thing refers to the process of splitting a data structure in two (2) parts to improve performance, but some conditions should be met in order for this approach to work efficiently: you need to have some kind of linked list, your data structure is bloated with members inside (size of data structure is on the large side), each data object has some kind of identifier (a key member) and a lot of searching/traversing back and forward over the linked list is done.

So, what we want to do is split the bloated data structure in two (2) parts. The first part (and small one) is called the Hot Node and it contains: the pointers (links) to the other nodes in the list, the key/ID that identifies the structure and a pointer to its Cold Node. The other part (the big one) is named the Cold Node and it carries the rest of the members from the original data structure. Therefore, if you combine each Hot Node with its corresponding Cold Node you get the original bloated data structure.

Ideally you would like to have all Hot Nodes stored close to each other in memory (data locality), that way traversing and searching the list is not that expensive (there should not be many cache misses). On the other hand, the Cold Nodes could be store anywhere in memory since they should only be fetch when the corresponding Hot Node was found.

 If you still don’t understand what all this I just talked about means, I suggest you watch the following video, it will explain it very clearly. Enjoy it!

See you soon! Adios!