{"id":309,"date":"2008-03-07T03:24:58","date_gmt":"2008-03-07T07:24:58","guid":{"rendered":"http:\/\/www.rakkar.org\/blog\/?p=309"},"modified":"2008-03-07T03:24:58","modified_gmt":"2008-03-07T07:24:58","slug":"data-structures-for-optimization","status":"publish","type":"post","link":"https:\/\/rakkar.org\/blog\/index.php\/2008\/03\/07\/data-structures-for-optimization\/","title":{"rendered":"Data structures for fun and optimization"},"content":{"rendered":"

\t\t\t\tI was updating the manual<\/a> for RakNet<\/a> and was reminded of how many data structures I’ve written for it.<\/p>\n

From the manual:<\/p>\n

DS_BinarySearchTree.h – Binary search tree<\/a>, and an AVL balanced<\/a> binary search tree.
\n DS_BPlusTree.h – BPlus tree<\/a> for fast lookup, delete, and insert.
\n DS_BytePool.h – Returns data blocks at certain size thresholds to reduce memory fragmentation.
\n DS_ByteQueue.h – A queue specialized for reading and writing bytes.
\n DS_Heap.h – Heap data structure<\/a>, includes both minheap and maxheap.
\n DS_HuffmanEncodingTree.h – Huffman encoding tree<\/a>, used to find the minimal bitwise representation given a frequency table.
\n DS_HuffmanEncodingTreeFactory.h – Creates instances of the Huffman encoding tree.
\n DS_HuffmanEncodingTreeNode.h – Node in the Huffman encoding tree.
\n DS_LinkedList.h – Standard linked list<\/a>.
\n DS_List.h – Dynamic array<\/a> (sometimes improperly called a vector). Also doubles as a stack<\/a>.
\n DS_Map.h – (Associative array<\/a>) Ordered list with an per-element sort key.
\n DS_MemoryPool.h – Allocate and free reused instances of a fixed size structure, used to reduce memory fragmentation.
\n DS_OrderedChannelHeap.h – Maxheap which returns a node based on the relative weight of the node’s associated channel. Used for task scheduling with priorities.
\n DS_OrderedList.h – List ordered by an arbitrary key via quicksort<\/a>.
\n DS_Queue.h – Standard queue<\/a> implemented with an array
\n DS_QueueLinkedList.h – Standard queue implemented with a linked list<\/a>
\n DS_RangeList.h – Stores a list of numerical values, and when the values are sequential, represents them as a range rather than individual elements. Useful when storing many values that are usually sequential.
\n DS_Table.h – Table<\/a> with columns and rows, and operations on that table.
\n DS_Tree.h – Noncyclic graph<\/a>
\n DS_WeightedGraph.h – Graph with weighted edges, used for routing via Dijkstra’s algorithm<\/a><\/p>\n

Data structures is one of the few classes in college that has a significant real-world bearing. It’s one of the cornerstones of good design and optimization.<\/p>\n

A few times I’ve been asked why I don’t just use STL.<\/p>\n

1. STL can cause linker errors
\n2. STL uses exceptions.
\n3. STL doesn’t have every feature I need.
\n4. I don’t know how well STL is optimized, but I know exactly how well my code is optimized.
\n5. In college I was confused for months before I figured out when people said ‘vector’ they meant ‘dynamic array.’ It became a pet-peeve of mine.
\n6. In college I started writing my own data structures before I knew STL existed. None of my classes ever covered it And once I started I had momentum to keep going.
\n5. It’s something I find interesting and enjoy writing.<\/p>\n

Aside from STL, of the game companies I’ve worked at, I’ve never seen any of them with as sophisticated a set of data structures as what I have in RakNet. When you need to process and track 30,000 messages a second you need heavy duty data structures like my memory-pool optimized B+ tree. Being able to support 30,000 messages vs. your standard game’s 20-30 messages a second is part of the polish you get with a dedicated mature library.\t\t<\/p>\n","protected":false},"excerpt":{"rendered":"

I was updating the manual for RakNet and was reminded of how many data structures I’ve written for it. From the manual: DS_BinarySearchTree.h – Binary search tree, and an AVL balanced binary search tree. DS_BPlusTree.h – BPlus tree for fast lookup, delete, and insert. DS_BytePool.h – Returns data blocks at certain size thresholds to reduce […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[2],"tags":[],"_links":{"self":[{"href":"https:\/\/rakkar.org\/blog\/index.php\/wp-json\/wp\/v2\/posts\/309"}],"collection":[{"href":"https:\/\/rakkar.org\/blog\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/rakkar.org\/blog\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/rakkar.org\/blog\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/rakkar.org\/blog\/index.php\/wp-json\/wp\/v2\/comments?post=309"}],"version-history":[{"count":0,"href":"https:\/\/rakkar.org\/blog\/index.php\/wp-json\/wp\/v2\/posts\/309\/revisions"}],"wp:attachment":[{"href":"https:\/\/rakkar.org\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=309"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/rakkar.org\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=309"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/rakkar.org\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=309"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}