← Back to index | Original Bugzilla link

Bug 14816 – improve dt_t data type for faster appending (tail list or array)

Status: RESOLVED
Resolution: FIXED
Severity: enhancement
Priority: P1
Component: dmd
Product: D
Version: D2
Platform: All
OS: All
Creation time: 2015-07-21T07:26:00Z
Last change time: 2017-01-13T08:23:45Z
Assigned to: nobody
Creator: code

Comments

Comment #0 by code — 2015-07-21T07:26:16Z

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

Comment #1 by code — 2015-07-21T07:40:26Z

Also see issue 14805.

Comment #2 by code — 2015-09-16T21:08:58Z

Partly fixed by https://github.com/D-Programming-Language/dmd/pull/5083.

Comment #3 by bugzilla — 2016-04-10T21:20:19Z

This is largely resolved by the DtBuilder changes.

Comment #4 by code — 2017-01-13T08:23:45Z

Yes DtBuilder has a tail list.