4 ms·
In most cases the performance penalty of having an extra internal array to keep track of insertion order is minimal, and the whole point of built-in collections
by gizmo 2y ago
In most cases the performance penalty of having an extra internal array to keep track of insertion order is minimal, and the whole point of built-in collections is so people can quickly write correct programs. When optimizing for performance default collections are likely to get replaced with hand-rolled versions anyway. But in all other cases a dictionary that “just works” is preferable to one that has such an annoying footgun that the go team had to randomize the iteration order in an attempt to treat the symptom instead of choosing correctness. Go isn’t even a high-performance language and many language design choices (channels!) explicit prioritize correctness over performance.
It’s like having an unstable sort as the default standard library sort function. People reasonably expect that when calling sort twice the second sort to do nothing, but you can always find people who will passionately argue that people deserve to get burned if they assume a sort function is stable.
- icholy 2y agoYeah, who needs O(1) deletes anyway? /s
- lifthrasiir 2y agoIn case you haven't realized yet, a hash table that maintains the insertion order can be still do O(1) deletes as long as the key order doesn't change arbitrarily after the initial insertion.
- icholy 2y agoI'm commenting on the proposed implementation of using an array to keep track of insertion order.
- lifthrasiir 2y agoAn array can be used to efficiently simulate a linked list and other data structure, however. (Or an intrusive linked list may be embedded into the bucket structure like PHP, but this is less efficient with open addressing scheme which is nowadays better for cache locality.)
- icholy 2y ago> An array can be used to efficiently simulate a linked list That's obviously not what the OP meant. Also, I don't think there's an efficient way of implementing deletes with an array backed linked list.
- mjevans 2y agoThat depends on what someone is willing to compromise. Extra space to point back at exactly that key (but that also needs to be updated each compaction?); personally I'd normally rather pay the lookup or key sort on iterator snapshot fee. An 'insert, or re-sorted order' side index which allows for nodes to be marked as 'deleted' (maybe nil / null, maybe a sentinel value meaning skip?); I might propose that to see if it fit the requirements well enough.
- icholy 2y ago... or just use a normal linked list with the existing entries like a sane person.