![]() Of course, you may want to simulate and measure your particular scenario with some throwaway test code to find the answer. So, linked lists are a nice way to implement an arbitrarily long first-in-first-out queue of large objects.Īnother thing to be careful about is that for small objects or where you allocate objects from a conventional heap instead of a custom free pool, arrays can be faster because copying isn't really that slow if it's not done that often, and the repeated allocation from the heap that a linked list would require every time a new element is added is slow. shifting all the elements in the queue whenever you insert/remove, which is slow for large objects.using a begin/end index pointer, which is fast but requires fixing the size of the queue so that the producer has to wait when the consumer's queue is full and locking the queue while the whole packet is filled if there is more than one producer.Only their pointers need to be updated.Īn array-based queue would have required: Linked lists are lightning fast for moving around objects like this, especially when the objects are large, since the objects don't actually have to move. Performing I/O basically involved grabbing a free packet from the beginning of the free list, configuring the packet, adding the packet to the device's list, and re-adding the packet to the beginning of the free pool when the I/O finished. I maintained a pool of free packets in another linked list. The controller serviced I/O requests for keyboard and disk using a linked list of packets in main memory. ![]() Implementing a high-level seemingly abstract data structure like a linked list in assembly isn't as hard as it sounds. I wrote a BIOS extension (basically a device driver for a BIOS, written in assembly) for a USB host controller.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |