[Issue 14816] New: improve dt_t data type for faster appending (tail list or array)
via Digitalmars-d-bugs
digitalmars-d-bugs at puremagic.com
Tue Jul 21 00:26:16 PDT 2015
https://issues.dlang.org/show_bug.cgi?id=14816
Issue ID: 14816
Summary: improve dt_t data type for faster appending (tail list
or array)
Product: D
Version: D2
Hardware: x86_64
OS: Linux
Status: NEW
Severity: enhancement
Priority: P1
Component: dmd
Assignee: nobody at puremagic.com
Reporter: code at dawg.eu
Right now dt_t [¹], used for to construct data output and initializers, uses a
singly linked list. This causes a lot of overhead b/c appending a single
element is O(N) making many output operations, e.g. an array, O(N^2).
We should at least use a list with tail pointer to have an O(1) append
operation.
It would be even better to use an array for better cache locality.
[¹]:
https://github.com/D-Programming-Language/dmd/blob/master/src/backend/cc.h#L1584
--
More information about the Digitalmars-d-bugs
mailing list