www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 14816] New: improve dt_t data type for faster appending (tail

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 puremagic.com
          Reporter: code 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

--
Jul 21 2015