3 ms·

These implementations are nicely written for learning purposes, but look inefficient. For example many of the data structures are implemented with a LinkedList

These implementations are nicely written for learning purposes, but look inefficient. For example many of the data structures are implemented with a LinkedList, but the allocations and pointer chasing is likely slower than just using arrays.

throwaway290 4y ago
Thank you!
imbnwa 4y ago
As a relative novice, I notice that a few animation libraries rely on linked lists for sequencing animations, and, as I understand it, React uses a linked list to implement the queue created from the Hooks calls in a component; is there no benefit to a linked list over an array that counters the downside of pointer chasing?
- esprehn 4y ago
  Libraries and frameworks generally use intrusive linked lists where the pointers are embedded inside the objects. That enables a lot of useful properties (like traversal) with minimal overhead. That's how the DOM and Layout is implemented in browsers as well. Link lists that use separate nodes (like the project in TFA) are rarely the best choice due to the performance trade offs and way modern CPUs work. This article explains it well: https://www.data-structures-in-practice.com/intrusive-linked-lists/ https://www.data-structures-in-practice.com/intrusive-linked... See also: https://github.com/trekhleb/javascript-algorithms/blob/bbbfd32a45a677950554a91c4ece8976b8b31c38/src/data-structures/linked-list/LinkedListNode.js#L1 https://github.com/trekhleb/javascript-algorithms/blob/bbbfd... https://github.com/trekhleb/javascript-algorithms/blob/bbbfd32a45a677950554a91c4ece8976b8b31c38/src/data-structures/linked-list/LinkedList.js#L4 https://github.com/trekhleb/javascript-algorithms/blob/bbbfd... Vs what React does: https://github.com/facebook/react/blob/657698e48d5b093b4ea5a7684e26d3fdd16695f2/packages/react-reconciler/src/ReactFiber.js#L148 https://github.com/facebook/react/blob/657698e48d5b093b4ea5a...
  - imbnwa 4y ago
    Very helpful, thank you
    - esprehn 4y ago
      I realize you mentioned hooks not react in general, that code is here: https://github.com/facebook/react/blob/657698e48d5b093b4ea5a7684e26d3fdd16695f2/packages/react-reconciler/src/ReactFiberHooks.js#L846 https://github.com/facebook/react/blob/657698e48d5b093b4ea5a... You can see the linked list insertion right below that too.

throwaway290 4y ago

Thank you!

imbnwa 4y ago

As a relative novice, I notice that a few animation libraries rely on linked lists for sequencing animations, and, as I understand it, React uses a linked list to implement the queue created from the Hooks calls in a component; is there no benefit to a linked list over an array that counters the downside of pointer chasing?

esprehn 4y ago
Libraries and frameworks generally use intrusive linked lists where the pointers are embedded inside the objects. That enables a lot of useful properties (like traversal) with minimal overhead. That's how the DOM and Layout is implemented in browsers as well. Link lists that use separate nodes (like the project in TFA) are rarely the best choice due to the performance trade offs and way modern CPUs work. This article explains it well: https://www.data-structures-in-practice.com/intrusive-linked-lists/ https://www.data-structures-in-practice.com/intrusive-linked... See also: https://github.com/trekhleb/javascript-algorithms/blob/bbbfd32a45a677950554a91c4ece8976b8b31c38/src/data-structures/linked-list/LinkedListNode.js#L1 https://github.com/trekhleb/javascript-algorithms/blob/bbbfd... https://github.com/trekhleb/javascript-algorithms/blob/bbbfd32a45a677950554a91c4ece8976b8b31c38/src/data-structures/linked-list/LinkedList.js#L4 https://github.com/trekhleb/javascript-algorithms/blob/bbbfd... Vs what React does: https://github.com/facebook/react/blob/657698e48d5b093b4ea5a7684e26d3fdd16695f2/packages/react-reconciler/src/ReactFiber.js#L148 https://github.com/facebook/react/blob/657698e48d5b093b4ea5a...
- imbnwa 4y ago
  Very helpful, thank you
  - esprehn 4y ago
    I realize you mentioned hooks not react in general, that code is here: https://github.com/facebook/react/blob/657698e48d5b093b4ea5a7684e26d3fdd16695f2/packages/react-reconciler/src/ReactFiberHooks.js#L846 https://github.com/facebook/react/blob/657698e48d5b093b4ea5a... You can see the linked list insertion right below that too.