[Issue 5813] [patch] std.array.Appender has severe performance and memory leak problems.
https://issues.dlang.org/show_bug.cgi?id=5813 --- Comment #21 from Andrei Alexandrescu --- What's the status of this? --
[Issue 5813] [patch] std.array.Appender has severe performance and memory leak problems.
https://issues.dlang.org/show_bug.cgi?id=5813 Andrei Alexandrescu changed: What|Removed |Added Keywords||bootcamp --
[Issue 5813] [patch] std.array.Appender has severe performance and memory leak problems.
https://issues.dlang.org/show_bug.cgi?id=5813 Jon Degenhardt changed: What|Removed |Added CC||jrdemail2000-dl...@yahoo.co ||m --
[Issue 5813] [patch] std.array.Appender has severe performance and memory leak problems.
https://issues.dlang.org/show_bug.cgi?id=5813 Jack Stouffer changed: What|Removed |Added CC||j...@jackstouffer.com Hardware|Other |All OS|Windows |All --
[Issue 5813] [patch] std.array.Appender has severe performance and memory leak problems.
https://issues.dlang.org/show_bug.cgi?id=5813 --- Comment #22 from Jack Stouffer --- https://github.com/dlang/phobos/pull/5115 --
[Issue 5813] [patch] std.array.Appender has severe performance and memory leak problems.
https://issues.dlang.org/show_bug.cgi?id=5813 Dmitry Olshansky changed: What|Removed |Added Status|NEW |RESOLVED CC||dmitry.o...@gmail.com Resolution|--- |WONTFIX --
[Issue 5813] [patch] std.array.Appender has severe performance and memory leak problems.
https://issues.dlang.org/show_bug.cgi?id=5813 j...@red.email.ne.jp changed: What|Removed |Added CC||j...@red.email.ne.jp --- Comment #23 from j...@red.email.ne.jp --- Summary: This is rather a DMD issue because the LDC's optimizer makes no performance change. OK? --
[Issue 5813] [patch] std.array.Appender has severe performance and memory leak problems.
http://d.puremagic.com/issues/show_bug.cgi?id=5813
--- Comment #1 from Rob Jacques 2011-05-20 10:29:57 PDT ---
*Update*
The previous version ended up having value semantics, not reference semantics,
due to the fact _tail wouldn't get updated and later nodes would be ignored.
For example:
auto test = Appender!string(16);
void func(Writer)(Writer w) {
w.put("The quick brown fox jumps over the lazy dog");
}
func(test);
assert(test.data == "The quick brown ");
//assert(test.data == "The quick brown fox jumps over the lazy dog");
I've updated the code to check/update tail lazily as needed. As an out of date
_tail naturally triggers memory allocation, this doesn't overly change the
performance of put on average.
==
struct Appender(A : T[], T) {
private {
enum PageSize = 4096; // Memory page size
alias Unqual!T E; // Internal element type
struct Data {
Data* next; // The next data segment
size_t capacity; // Capacity of this segment
E[] arr;// This segment's array
// Initialize a segment using an existing array
void opAssign(E[] _arr) {
next = null;
capacity = _arr.capacity;
arr= _arr;
if(_arr.length < capacity) {
arr.length = capacity;
arr.length = _arr.length;
}
assert(_arr.ptr is arr.ptr,"Unexpected reallocation occurred");
}
// Create a new segment using an existing array
this(Unqual!T[] _arr) { this = _arr; }
// Create a new segment with at least size bytes
this(size_t size) {
if(size > PageSize)
size = (size + PageSize-1) & ~(PageSize-1);
auto bi = GC.qalloc(size, !hasIndirections!T * 2);
next = null;
capacity = bi.size / T.sizeof;
arr = (cast(E*)bi.base)[0..0];
static assert(!false*2 == GC.BlkAttr.NO_SCAN);
}
}
Data* _head = null; // The head data segment
Data* _tail = null; // The last data segment
// Returns: the total number of elements in the appender
size_t _length() {
size_t len = 0;
for(auto d = _head; d !is null; d = d.next)
len += d.arr.length;
return len;
}
// Flatten all the data segments into a single array
E[] flatten() {
if(!_head) return null;
if( _head && _head.next is null)
return _head.arr;
size_t N = _length;
size_t len = N;
size_t i = 0;
auto arr = new E[N];
for(auto d = _head; N > 0; d = d.next, N -= len, i += len) {
len= min(N, d.arr.length);
memcpy(arr.ptr+i, d.arr.ptr, len * T.sizeof);
}
return arr;
}
// Returns: the next capacity size
size_t nextCapacity() nothrow pure {
auto cap = _tail.capacity * T.sizeof * 2;
return cap < PageSize ? cap : PageSize;
}
}
/** Construct an appender with a given array. Note that this does not copy
* the data. If the array has a larger capacity as determined by
* arr.capacity, it will be used by the appender. After initializing an
* appender on an array, appending to the original array will reallocate.
*/
this(T[] arr) {
if(arr is null) _head = _tail = new Data( 16 * T.sizeof );
else_head = _tail = new Data( cast(E[]) arr );
}
/// Construct an appender with a capacity of at least N elements.
this(size_t N) { _head = _tail = new Data( N * T.sizeof ); }
/// Returns: the maximum length that can be accommodated without allocation
size_t capacity() {
size_t cap = 0;
for(auto d = _head; d !is null; d = d.next)
cap += d.capacity;
return cap;
}
/// Returns: a mutable copy of the data.
E[] dup() {
if(_head && _head.next is null)
return flatten.dup;
return flatten;
}
/// Returns: a immutable copy of the data.
immutable(E)[] idup() {
return cast(immutable(E)[]) dup;
}
/// Returns: the appender's data as an array.
T[] data() {
auto arr = flatten;
if(_head !is _tail) {
*_head = arr;
_tail = _head;
}
return cast(T[]) arr;
}
/** Reserve at least newCapacity elements for appending. Note that more
* elements may be reserved than requested. If newCapacity < capacity,
* then nothing is
[Issue 5813] [patch] std.array.Appender has severe performance and memory leak problems.
http://d.puremagic.com/issues/show_bug.cgi?id=5813 --- Comment #2 from Rob Jacques 2011-06-09 11:11:16 PDT --- This patch passes the unittests listed in Issue 5663 - std.array.Appender.put bug -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 5813] [patch] std.array.Appender has severe performance and memory leak problems.
http://d.puremagic.com/issues/show_bug.cgi?id=5813 Steven Schveighoffer changed: What|Removed |Added CC||schvei...@yahoo.com --- Comment #3 from Steven Schveighoffer 2011-06-09 11:58:55 PDT --- I think this is a good idea to do, but the code is somewhat obfuscated. For example, you are returning a value from a void function (extend), and doing some weird shortcuts (like !false*2). There are also some style differences from the current D style guidelines. These will have to be fixed before it's put into phobos. One technical point -- the limit of multiples of page sizes when requesting more than one page is already done by the GC. That is, If you request more than 1/2 page, you will get a multiple of pages. I think the code will perform exactly as well if the multiple-of-page limitation is removed from your code, and this then does not make any assumptions about how big a page size is (if it ever changes). Do you want to do a pull request and have the code reviewed? I think it's definitely worth changing Appender to do this. One further thing -- I planned on making two versions of Appender: one that is a reference type, and one that is not. The version that is not should allow filling an existing an array without allocating anything. The current Appender (the one in phobos now) always allocates an pImpl struct, even if the array never needs to be extended. The tradeoff is that the non-reference appender is not returnable, and you can't make copies of it (i.e. this(this) is @disabled). Is this possible with your code? If so, and it's easy enough, can you create a version that does this too? -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 5813] [patch] std.array.Appender has severe performance and memory leak problems.
http://d.puremagic.com/issues/show_bug.cgi?id=5813 --- Comment #4 from Rob Jacques 2011-06-09 12:40:52 PDT --- (In reply to comment #3) > I think this is a good idea to do, but the code is somewhat obfuscated. For > example, you are returning a value from a void function (extend), and doing > some weird shortcuts (like !false*2). There are also some style differences > from the current D style guidelines. These will have to be fixed before it's > put into phobos. The obfuscation generally comes from a desire to minimize multi-lines to one-liners. But if you think these are too compressed, I'll change them to something cleaner. Regarding D style guidelines, there has been so much discussion over them, that I don't know if/where there current guidelines exist/are. And the existing Phobos codebase is a mash-up of different styles. I mean, even ddoc comments vary between /++ and /**. Is there anything in particular you'd recommend I'd change? > One technical point -- the limit of multiples of page sizes when requesting > more than one page is already done by the GC. That is, If you request more > than 1/2 page, you will get a multiple of pages. I think the code will > perform > exactly as well if the multiple-of-page limitation is removed from your code, > and this then does not make any assumptions about how big a page size is (if > it > ever changes). Thank you. I'll remove that line. > Do you want to do a pull request and have the code reviewed? I think it's > definitely worth changing Appender to do this. Yes, but I haven't gotten around to learning/installing Git on Windows yet. > One further thing -- I planned on making two versions of Appender: one that is > a reference type, and one that is not. The version that is not should allow > filling an existing an array without allocating anything. The current > Appender > (the one in phobos now) always allocates an pImpl struct, even if the array > never needs to be extended. > > The tradeoff is that the non-reference appender is not returnable, and you > can't make copies of it (i.e. this(this) is @disabled). > > Is this possible with your code? If so, and it's easy enough, can you create > a > version that does this too? The simple solution would be to emplace the first data node inside the appender struct. But I'm not sure the benefit of such a solution: appender always checks/extends-to the capacity of an array, which involves taking the GC lock, etc. So since the taking lock can't be averted, avoiding an extra 16-byte allocation isn't much worse. But I can always implement it using a template parameter + static ifs, so it shouldn't be hard to try it out. Hmm... I could also fold in RefAppender that way. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 5813] [patch] std.array.Appender has severe performance and memory leak problems.
http://d.puremagic.com/issues/show_bug.cgi?id=5813 --- Comment #5 from Steven Schveighoffer 2011-06-09 14:22:32 PDT --- (In reply to comment #4) > The obfuscation generally comes from a desire to minimize multi-lines to > one-liners. I don't mind the one-liners, but things like !hasIndirections!T*2 is better written as hasIndirections!T ? 0 : GC.BlkAttr.NO_SCAN. It's more decipherable and self-documenting. Shortcuts that hide the intention of the code are not worth it. The one-liners that assign to several things at once are at least clear. Although I think this one should be split into at least two statements: return _tail = _tail.next = new Data( size ); > Regarding D style guidelines, there has been so much > discussion over them, that I don't know if/where there current guidelines > exist/are. And the existing Phobos codebase is a mash-up of different styles. > I > mean, even ddoc comments vary between /++ and /**. Is there anything in > particular you'd recommend I'd change? I think the best thing to do for now is to follow the style of the original code. TBH, I'd say submit the pull request and the review will flesh out individual things that should be fixed (the github review process is really good). > > Do you want to do a pull request and have the code reviewed? I think it's > > definitely worth changing Appender to do this. > > Yes, but I haven't gotten around to learning/installing Git on Windows yet. Highly recommend progit.org for learning git. Just getting git working on Windows myself... > The simple solution would be to emplace the first data node inside the > appender > struct. But I'm not sure the benefit of such a solution: appender always > checks/extends-to the capacity of an array, which involves taking the GC lock, > etc. So since the taking lock can't be averted, avoiding an extra 16-byte > allocation isn't much worse. But I can always implement it using a template > parameter + static ifs, so it shouldn't be hard to try it out. Hmm... I could > also fold in RefAppender that way. You are probably right, I added the code to fill to capacity after thinking about creating such a type. The capacity check definitely needs to take the global lock. Maybe the non-reference appender would not try to expand to capacity (that is, after all, an optimization). In any case, this isn't as important as the other fixes you've already created. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 5813] [patch] std.array.Appender has severe performance and memory leak problems.
http://d.puremagic.com/issues/show_bug.cgi?id=5813 Vladimir Panteleev changed: What|Removed |Added CC||thecybersha...@gmail.com --- Comment #6 from Vladimir Panteleev 2011-12-02 02:45:59 PST --- What's this status of this patch? Note that today, it's extremely unlikely for patches from Bugzilla to be incorporated unless someone creates a GitHub pull request for them. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 5813] [patch] std.array.Appender has severe performance and memory leak problems.
http://d.puremagic.com/issues/show_bug.cgi?id=5813 --- Comment #7 from Steven Schveighoffer 2011-12-02 04:49:25 PST --- I think we were waiting on Rob to change this into a pull request. Not sure if that's going to happen? -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 5813] [patch] std.array.Appender has severe performance and memory leak problems.
http://d.puremagic.com/issues/show_bug.cgi?id=5813 --- Comment #8 from Rob Jacques 2011-12-02 05:38:25 PST --- I'm planning on putting in a pull request for this, probably sometime over the Christmas holidays(I hope). Currently, I'm in the middle of finishing up my Ph.D. thesis and moving to a new city and job, so my bandwidth is very limited at the moment. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 5813] [patch] std.array.Appender has severe performance and memory leak problems.
http://d.puremagic.com/issues/show_bug.cgi?id=5813 --- Comment #9 from Vladimir Panteleev 2011-12-02 10:33:44 PST --- I did some benchmarks with this and some other variants. At least for small strings, this code performs worse than the current appender. Judging by the description it's optimized for large blocks of data, but in the case of many small strings it can perform as bad as 50% worse than the current appender for typical cases (e.g. building a few KB of HTML). Here is my test code: http://dump.thecybershadow.net/a05a2c4dc7cd2a8e21b3a447c7eff150/test2.d http://dump.thecybershadow.net/eff5c7ef81e18bf75d8462ffe16a52e4/appender.d I was able to get 25% more performance for my test case from the standard appender by adding a method that accepts multiple arguments (which preallocates only once). My code is a hack, but it would be nice to see something like that in the official appender. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 5813] [patch] std.array.Appender has severe performance and memory leak problems.
http://d.puremagic.com/issues/show_bug.cgi?id=5813 --- Comment #10 from Rob Jacques 2011-12-02 12:35:48 PST --- (In reply to comment #9) > I did some benchmarks with this and some other variants. > > At least for small strings, this code performs worse than the current > appender. > Judging by the description it's optimized for large blocks of data, but in the > case of many small strings it can perform as bad as 50% worse than the current > appender for typical cases (e.g. building a few KB of HTML). > > Here is my test code: > > http://dump.thecybershadow.net/a05a2c4dc7cd2a8e21b3a447c7eff150/test2.d > http://dump.thecybershadow.net/eff5c7ef81e18bf75d8462ffe16a52e4/appender.d > > I was able to get 25% more performance for my test case from the standard > appender by adding a method that accepts multiple arguments (which > preallocates > only once). My code is a hack, but it would be nice to see something like that > in the official appender. Thank you for the additional benchmarks. The primary purpose of my code was to optimize for memory usage, which in turn optimizes for computation/performance (i.e. number of main memory copies and memory allocations). And, I also optimized appender for use as a dynamic buffer. But this is all big-O stuff. I did include a short string test in my benchmark set while I was optimizing the code; my first implementations (never posted) did have some major slow downs, which I fixed by re-working the put routine. So there still might still be some little-o issues there. And I will definitely add a void put(U...)(U items) overload. I don't think it would affect this benchmark in any ways, but my appender is somewhat dependent on my patch to put (Issue 5233). I've run your benchmarks and played with them a little bit. Running the benchmarks sequentially is definitely generating GC warm-up issues. I've recommend running them cold in the future, though the qualitative results are the same and cold runs are the ideal situation for the old appender. I want to rewrite my __ctfe version appender, since Don added support for structs and new, so I'll also look at the short string performance of appender while I'm at it I'll do some profiling and look into this some more. I'd really like for appender to be the right solution for anything bigger than `hello` ~ `world`. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 5813] [patch] std.array.Appender has severe performance and memory leak problems.
http://d.puremagic.com/issues/show_bug.cgi?id=5813 --- Comment #11 from Rob Jacques 2011-12-02 21:10:23 PST --- I did some more digging. I reworked the put routine itself and changed the growth strategy to be as aggressive as the original appender. This got me down from a 52% slowdown, to a 20% slowdown. I've still have more work to do, but to put this into perspective, a 20% slowdown is equivalent to adding an extra if conditional to the put routine. Again, thanks Vladimir for these benchmarks. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 5813] [patch] std.array.Appender has severe performance and memory leak problems.
http://d.puremagic.com/issues/show_bug.cgi?id=5813 --- Comment #12 from Vladimir Panteleev 2011-12-28 14:56:17 PST --- I spent some more time working on an optimized appender. Things I found: 1) Extra indirection levels are performance killers 2) I failed to create a chained appender (like the one in this patch) that was faster than a copying one, for my test cases 3) At least on Windows and with short strings, simple slice copy trumps all memcpy implementations I tried 4) You can write a nextCapacity function with no branches 5) It's better to store an "end" pointer than a "capacity" integer I put all my attempts and benchmarking code here: https://github.com/CyberShadow/DAppenderResearch The version I went with is based on fastappender2 in that repo. The final version is here: https://github.com/CyberShadow/ae/blob/master/utils/appender.d For a chained appender, I would move the tail members into the main structure. My attempt at a fast chained appender is in fastappender4. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 5813] [patch] std.array.Appender has severe performance and memory leak problems.
http://d.puremagic.com/issues/show_bug.cgi?id=5813 Andrei Alexandrescu changed: What|Removed |Added CC||and...@metalanguage.com --- Comment #13 from Andrei Alexandrescu 2011-12-29 11:58:44 PST --- Great work! Why not a pull request? -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 5813] [patch] std.array.Appender has severe performance and memory leak problems.
http://d.puremagic.com/issues/show_bug.cgi?id=5813 --- Comment #14 from Vladimir Panteleev 2011-12-29 22:28:34 PST --- My code is more of a research project. It can't be safely copied, only supports items 1 byte in size, and doesn't care much in terms of UTF encoding. So, it can't be a drop-in replacement without a lot of hammering, and even then you have to decide whether you want it to be fast or copyable. I hope my research will be useful for others (like Rob) trying to improve the Phobos appender, though. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 5813] [patch] std.array.Appender has severe performance and memory leak problems.
http://d.puremagic.com/issues/show_bug.cgi?id=5813 --- Comment #15 from Rob Jacques 2012-01-02 12:02:40 PST --- Vladimir, the code in https://github.com/CyberShadow/ae/blob/master/utils/appender.d seems to be under the MPL, which isn't Phobos compatible. What license is the code in: https://github.com/CyberShadow/DAppenderResearch under? If it's not under a Boost compatible license, could you make it available under one? Thanks for all this work. (In reply to comment #12) > 1) Extra indirection levels are performance killers I agree. > 2) I failed to create a chained appender (like the one in this patch) that was > faster than a copying one, for my test cases The primary purpose of a chained appender is to minimize memory leaks, memory usage and maximizing large scale performance. That said, I did write a faster chained appender for your benchmarks; however I did this by initializing the appender with a page of memory, which definitely should not be the default behavior. That said, one viable strategy for appender would be to keep 1 page of memory around as a scratch pad. > 3) At least on Windows and with short strings, simple slice copy trumps all > memcpy implementations I tried > 4) You can write a nextCapacity function with no branches Good to know. > 5) It's better to store an "end" pointer than a "capacity" integer I'll look into this, but this you can not make this judgment call based on the performance of a char appender. The issue is that anything with a power of 2 T.sizeof performs integer multiplication/division using shift operations instead of the actual underlying instructions, both of which are very slow. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 5813] [patch] std.array.Appender has severe performance and memory leak problems.
http://d.puremagic.com/issues/show_bug.cgi?id=5813 --- Comment #16 from Vladimir Panteleev 2012-01-02 12:10:18 PST --- (In reply to comment #15) > Vladimir, the code in > https://github.com/CyberShadow/ae/blob/master/utils/appender.d > seems to be under the MPL, which isn't Phobos compatible. What license is the > code in: > https://github.com/CyberShadow/DAppenderResearch > under? If it's not under a Boost compatible license, could you make it > available under one? Sure, consider my code in DAppenderResearch public domain. ae is mainly MPL because it was the least restrictive license other contributors agreed on. > That said, I did write a faster > chained appender for your benchmarks; however I did this by initializing the > appender with a page of memory, which definitely should not be the default > behavior. That said, one viable strategy for appender would be to keep 1 page > of memory around as a scratch pad. Can you elaborate on this (or share your code)? > > 5) It's better to store an "end" pointer than a "capacity" integer > I'll look into this, but this you can not make this judgment call based on the > performance of a char appender. The issue is that anything with a power of 2 > T.sizeof performs integer multiplication/division using shift operations > instead of the actual underlying instructions, both of which are very slow. I'm not following your explanation. I don't see how element size plays against my conclusion - in fact, as far as I can see, calculating a "position-after-append" pointer and comparing it to an "end" pointer is going to be faster, because you will need to update the position anyway. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 5813] [patch] std.array.Appender has severe performance and memory leak problems.
http://d.puremagic.com/issues/show_bug.cgi?id=5813
--- Comment #17 from Rob Jacques 2012-01-02 13:16:19 PST ---
> > That said, I did write a faster
> > chained appender for your benchmarks; however I did this by initializing the
> > appender with a page of memory, which definitely should not be the default
> > behavior. That said, one viable strategy for appender would be to keep 1
> > page
> > of memory around as a scratch pad.
>
> Can you elaborate on this (or share your code)?
For part 1 (fastest possible 'chained' appender): Simply construct specifying a
large number of elements. i.e.
auto app = Appender!string(4096);
FastestAppender7 seems to do something similar (enum MIN_SIZE = 4096;)
As for part 2 (fastest practical 'chained' appender) I haven't written it yet.
In essence you'd have two TLS variables, a scratch node and memory page and an
in use flag.
private static void* __Appender_scratch_node;
private static bool __Appender_scratch_in_use;
Appender(T) {...}
Then when appender is constructed instead of creating a new node and a little
bit of ram each time, a single node and 1 page of memory would be reused. The
boolean flag would prevent a second appender from reusing the same scratch pad;
(I figure 2+ appenders would be relatively rare). Then, when data is called a
single copy would be made of the correct length (Appending after data should
also be relatively rare).
> > > 5) It's better to store an "end" pointer than a "capacity" integer
> > I'll look into this, but this you can not make this judgment call based on
> > the
> > performance of a char appender. The issue is that anything with a power of 2
> > T.sizeof performs integer multiplication/division using shift operations
> > instead of the actual underlying instructions, both of which are very slow.
>
> I'm not following your explanation. I don't see how element size plays against
> my conclusion - in fact, as far as I can see, calculating a
> "position-after-append" pointer and comparing it to an "end" pointer is going
> to be faster, because you will need to update the position anyway.
I'm referring to the fact that ptr + i => cast(T*)(cast(size_t)ptr +
i*T.sizeof) and ptrA - ptrB => (cast(size_t)ptrA - cast(size_t)ptrB) /
T.sizeof. Which can lead to a subtle performance issues when T.sizeof != 1 or a
power of 2. But, my first code review doesn't reveal any worrying usages in the
primary code path; most cases of ptrA-ptrB seem to be behind rarely used if
conditionals.
P.S.
Regarding your previous assertion:
> 4) You can write a nextCapacity function with no branches
I'm having trouble finding this in the code. All I can find is:
auto newCapacity = newSize < MIN_SIZE ? MIN_SIZE : newSize * 2;
which contains a branch. (i.e. the ?: operator).
Also, I know understand better what you meant by
> 1) Extra indirection levels are performance killers
Unfortunately, your attempt to reduce the number of indirections has broken one
of the invariants of Appender; specifically that it is a reference type.
Putting cursors, etc. into the Appender struct will result in data stomping.
--
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
--- You are receiving this mail because: ---
[Issue 5813] [patch] std.array.Appender has severe performance and memory leak problems.
http://d.puremagic.com/issues/show_bug.cgi?id=5813 --- Comment #18 from Vladimir Panteleev 2012-01-02 13:32:01 PST --- (In reply to comment #17) > For part 1 (fastest possible 'chained' appender): Simply construct specifying > a > large number of elements. i.e. > auto app = Appender!string(4096); > FastestAppender7 seems to do something similar (enum MIN_SIZE = 4096;) The 4th one does that too, albeit implicitly. MIN_SIZE is half a page, but it will always allocate a little over that; which will cause the GC to return a whole page. MIN_SIZE was chosen to be the smallest size that results in an expandable allocation. Note that the 7th experiment is the least GC-friendly of the whole. > As for part 2 (fastest practical 'chained' appender) I haven't written it yet. > In essence you'd have two TLS variables, a scratch node and memory page and an > in use flag. Sounds like a nice idea. > I'm referring to the fact that ptr + i => cast(T*)(cast(size_t)ptr + > i*T.sizeof) and ptrA - ptrB => (cast(size_t)ptrA - cast(size_t)ptrB) / > T.sizeof. Which can lead to a subtle performance issues when T.sizeof != 1 or > a > power of 2. But, my first code review doesn't reveal any worrying usages in > the > primary code path; most cases of ptrA-ptrB seem to be behind rarely used if > conditionals. Yes, that was my point. Only one multiplication by T.sizeof and one branch are necessary on the hot path when appending a single item (I see that my code doesn't follow this due to its usage of slice copies). I wonder if putting the "cursorEnd > end" check inside the per-item loop in such cases would be faster - it would be exchanging a multiplication with a branch. > Regarding your previous assertion: > > 4) You can write a nextCapacity function with no branches > I'm having trouble finding this in the code. All I can find is: > > auto newCapacity = newSize < MIN_SIZE ? MIN_SIZE : newSize * 2; > > which contains a branch. (i.e. the ?: operator). The main idea is in fastappender2.d. The "if" at the start can be replaced with another bitwise or. It doesn't even matter, because that code will not be executed as often to make a significant difference; I stated it more as a curiosity. > Also, I know understand better what you meant by > > 1) Extra indirection levels are performance killers > Unfortunately, your attempt to reduce the number of indirections has broken > one > of the invariants of Appender; specifically that it is a reference type. > Putting cursors, etc. into the Appender struct will result in data stomping. I know, I said so in my answer to Andrei's comment. This is fine for my uses. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 5813] [patch] std.array.Appender has severe performance and memory leak problems.
http://d.puremagic.com/issues/show_bug.cgi?id=5813 --- Comment #19 from Rob Jacques 2012-03-19 14:02:01 PDT --- https://github.com/D-Programming-Language/phobos/pull/502 -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 5813] [patch] std.array.Appender has severe performance and memory leak problems.
http://d.puremagic.com/issues/show_bug.cgi?id=5813 bearophile_h...@eml.cc changed: What|Removed |Added CC||bearophile_h...@eml.cc --- Comment #20 from bearophile_h...@eml.cc 2012-03-19 15:13:08 PDT --- (In reply to comment #19) > https://github.com/D-Programming-Language/phobos/pull/502 > Algorithmically, Appender is implemented using a sealed rope, > a linked-list of arrays, with the first node being cached in > a thread local free list. Was a linked-list of arrays better/faster than a dynamic array of pointers to equal-sized memory blocks (decks data structure)? -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email --- You are receiving this mail because: ---
[Issue 5813] [patch] std.array.Appender has severe performance and memory leak problems.
https://issues.dlang.org/show_bug.cgi?id=5813 Issue 5813 depends on issue 5233, which changed state. Issue 5233 Summary: [patch] std.range.put accepts *any* element type when putting to an array. https://issues.dlang.org/show_bug.cgi?id=5233 What|Removed |Added Status|ASSIGNED|RESOLVED Resolution|--- |FIXED --
