www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Use case: eliminate hidden allocations in buildPath

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Hello,


Walter and I were talking about eliminating the surreptitious 
allocations in buildPath:

http://dlang.org/phobos/std_path.html#.buildPath

We'd need to keep the existing version working, so we're looking at 
adding one or more new overloads. We're looking at giving the user the 
option to control any needed memory allocation (or even arrange things 
such that there's no memory allocated at all).

It's a generous design space, so although we have a couple of ideas 
let's hear others first.


Thanks,

Andrei
Dec 04 2013
next sibling parent reply Michel Fortin <michel.fortin michelf.ca> writes:
On 2013-12-04 23:14:48 +0000, Andrei Alexandrescu 
<SeeWebsiteForEmail erdani.org> said:

 Walter and I were talking about eliminating the surreptitious 
 allocations in buildPath:
 
 http://dlang.org/phobos/std_path.html#.buildPath
 
 We'd need to keep the existing version working, so we're looking at 
 adding one or more new overloads. We're looking at giving the user the 
 option to control any needed memory allocation (or even arrange things 
 such that there's no memory allocated at all).
 
 It's a generous design space, so although we have a couple of ideas 
 let's hear others first.
Allow an allocator as the first argument. Then pass an allocator that uses preallocated memory (or any other strategy that does not really need to allocate). While technically the allocator still "allocates" memory, since you control the allocator it does it the you can redefine "allocate" to not allocate. Here's a funny thought: allow plain arrays to be *typed* allocators through UFCS, just like arrays are ranges. If you have an array of chars, then "allocating" from it will simply return a slice and "bump the pointer" by becoming the remaining unused slice. The big problem with buildPath is that it won't work with overloading because your allocator has the same type as the other parameters. You'll need to wrap it in some kind of allocator shell. :-/ -- Michel Fortin michel.fortin michelf.ca http://michelf.ca
Dec 04 2013
parent reply Manu <turkeyman gmail.com> writes:
On 5 December 2013 10:13, Michel Fortin <michel.fortin michelf.ca> wrote:

 On 2013-12-04 23:14:48 +0000, Andrei Alexandrescu <
 SeeWebsiteForEmail erdani.org> said:

  Walter and I were talking about eliminating the surreptitious allocations
 in buildPath:

 http://dlang.org/phobos/std_path.html#.buildPath

 We'd need to keep the existing version working, so we're looking at
 adding one or more new overloads. We're looking at giving the user the
 option to control any needed memory allocation (or even arrange things such
 that there's no memory allocated at all).

 It's a generous design space, so although we have a couple of ideas let's
 hear others first.
Allow an allocator as the first argument. Then pass an allocator that uses preallocated memory (or any other strategy that does not really need to allocate). While technically the allocator still "allocates" memory, since you control the allocator it does it the you can redefine "allocate" to not allocate.
Allocator as the first argument? This is so you can use UFCS on the allocator to make the call? I think it maybe makes sense for a function that takes an output range to receive it as the first argument for this reason: outputRange.myFunction(); // I'm not sure if I like this, not sure it's communicating the right process... but maybe people find it convenient? An overload that receives an allocator though, I'd probably make the allocator the last argument, this way it can have a default arg that is the default GC allocator, thus eliminating the other (original?) overload of the function which receives neither an output range or an allocator (using the GC intrinsically). Here's a funny thought: allow plain arrays to be *typed* allocators through
 UFCS, just like arrays are ranges. If you have an array of chars, then
 "allocating" from it will simply return a slice and "bump the pointer" by
 becoming the remaining unused slice. The big problem with buildPath is that
 it won't work with overloading because your allocator has the same type as
 the other parameters. You'll need to wrap it in some kind of allocator
 shell. :-/
I'm not sure I like this idea. I think I'd prefer to see 2 overloads, one that receives an output range, and one that receives an allocator (which may default to a GC allocator?).
Dec 04 2013
parent reply Michel Fortin <michel.fortin michelf.ca> writes:
On 2013-12-05 02:24:02 +0000, Manu <turkeyman gmail.com> said:

 Allocator as the first argument? This is so you can use UFCS on the
 allocator to make the call?
Haha, no. That's because buildPath's arguments are (const(C[])[] paths...) with a "..." at the end. Can we put an argument after the variadic argument? I didn't check, but I though it was impossible... thus the allocator as the first argument. -- Michel Fortin michel.fortin michelf.ca http://michelf.ca
Dec 04 2013
next sibling parent Manu <turkeyman gmail.com> writes:
On 5 December 2013 13:14, Michel Fortin <michel.fortin michelf.ca> wrote:

 On 2013-12-05 02:24:02 +0000, Manu <turkeyman gmail.com> said:

  Allocator as the first argument? This is so you can use UFCS on the
 allocator to make the call?
Haha, no. That's because buildPath's arguments are (const(C[])[] paths...) with a "..." at the end. Can we put an argument after the variadic argument? I didn't check, but I though it was impossible... thus the allocator as the first argument.
Oh yeah! :P I was thinking in a more general sense, as a principle to be applied across phobos, not just for this one function.
Dec 04 2013
prev sibling parent Jacob Carlborg <doob me.com> writes:
On 2013-12-05 04:14, Michel Fortin wrote:

 Haha, no. That's because buildPath's arguments are (const(C[])[]
 paths...) with a "..." at the end. Can we put an argument after the
 variadic argument? I didn't check, but I though it was impossible...
 thus the allocator as the first argument.
No, that's not possible. One could think it would be, as long as there is no conflict in the types. -- /Jacob Carlborg
Dec 05 2013
prev sibling next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Wed, Dec 04, 2013 at 03:14:48PM -0800, Andrei Alexandrescu wrote:
 Hello,
 
 
 Walter and I were talking about eliminating the surreptitious
 allocations in buildPath:
 
 http://dlang.org/phobos/std_path.html#.buildPath
 
 We'd need to keep the existing version working, so we're looking at
 adding one or more new overloads. We're looking at giving the user
 the option to control any needed memory allocation (or even arrange
 things such that there's no memory allocated at all).
 
 It's a generous design space, so although we have a couple of ideas
 let's hear others first.
[...] What about a new overload that takes an output range instead of returning a string? The caller can then create the appropriate output range that does whatever is desired (malloc a buffer, use a static fixed-size buffer, etc.), and buildPath doesn't have to care about the implementation details. So, something like: void buildPath(OutputRange,Range)(OutputRange output, Range segments) if (isOutputRange!(OutputRange, ElementType!Range)) { ... } // On a related note, I wonder if it's profitable to extend the concept of an output range to include void delegates that take range elements as arguments. The current toString overload looked for by std.format, for example, has this signature: void toString(scope void delegate(const(char)[] s) dg); The delegate here essentially behaves like an output range (it takes snippets of string data and presumably appends them to some buffer somewhere). So why not extend the concept of output ranges to include such delegates, so that we can write: void toString(R)(R r) if (isOutputRange!R); Then any output range can be used as the target of a string conversion, e.g., writing straight to a file or network socket without the unnecessary buffering that returning a string implies. "But!" I hear you cry, "you can't call a delegate as dg.put(...), which you have to if it is to conform to the output range interface!" To that I'd say: module std.range; ... void put(R,T)(R dg, T data) if (is(R == void delegate(T)) || is(R == void function(T))) { dg(data); } If I'm not mistaken, this should make isOutputRange true for functions and delegates that take the appropriate argument types. This then allows us to use buildPath with no hidden allocations, for example: char[1024] buffer; void appendToBuf(const(char)[] data) { ... } void main() { buildPath(&appendToBuf, "usr", "local", "share", "filename"); } T -- Three out of two people have difficulties with fractions. -- Dirk Eddelbuettel
Dec 04 2013
prev sibling next sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Wednesday, December 04, 2013 16:38:54 H. S. Teoh wrote:
 What about a new overload that takes an output range instead of
 returning a string?
I would have thought that that would be the obvious way to solve the problem. In general, I think that when a function allocates any kind of string or array which it returns, we should overload it with a version that takes an output range. In many cases, it would probably even make sense to make the default just use std.array.appender and make it so that only the output range overload is really doing any work. What to do in cases of allocation where we're not dealing with arrays being returned is a tougher question, and I think that that starts going into custom allocator territory, but for arrays, output ranges are definitely the way to go IMHO. - Jonathan M Davis
Dec 04 2013
prev sibling next sibling parent Manu <turkeyman gmail.com> writes:
On 5 December 2013 11:02, Jonathan M Davis <jmdavisProg gmx.com> wrote:

 On Wednesday, December 04, 2013 16:38:54 H. S. Teoh wrote:
 What about a new overload that takes an output range instead of
 returning a string?
I would have thought that that would be the obvious way to solve the problem. In general, I think that when a function allocates any kind of string or array which it returns, we should overload it with a version that takes an output range. In many cases, it would probably even make sense to make the default just use std.array.appender and make it so that only the output range overload is really doing any work.
This seems the intuitive approach to me. What to do in cases of allocation where we're not dealing with arrays being
 returned is a tougher question, and I think that that starts going into
 custom
 allocator territory, but for arrays, output ranges are definitely the way
 to go
 IMHO.
You mean for internal working buffers? It get's tricky. In my experience, many functions can use alloca, with a fallback in the event of very large workspaces. In the event of very large workspaces, it is often possible to break the process into stages which allow an iterative use of a smaller alloca-ed buffer if the function doesn't perform highly random access on the working data. In the event of large workspace and heavily randomised access to the working dataset (ie, difficult to avoid one large allocation), then and only then, maybe start thinking about receiving an allocator to work with (default arg to a gc allocator), or, if it's a large complex process, break the process into sub-functions which the user can issue, and they will then inherit ownership and management of the workspace, which they can treat how they like. These are some of my approaches. Almost all code I write must never allocate, except for functions that produce new allocations, where either receiving an output range or an allocator seems intuitive. The most important question to ask is 'can this function possibly be called recursively?'. Many library functions are effectively leaf functions, and can't lead back into user code via any path, which means alloca is safe to use liberally. If there is potential for a recursive call, then i guess you need to start preferring receiving allocators or output ranges, unless the alloca is in the order of a normal function's stack usage (<1kb-ish?).
Dec 04 2013
prev sibling next sibling parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Wednesday, 4 December 2013 at 23:14:48 UTC, Andrei 
Alexandrescu wrote:
 Hello,


 Walter and I were talking about eliminating the surreptitious 
 allocations in buildPath:

 http://dlang.org/phobos/std_path.html#.buildPath

 We'd need to keep the existing version working, so we're 
 looking at adding one or more new overloads. We're looking at 
 giving the user the option to control any needed memory 
 allocation (or even arrange things such that there's no memory 
 allocated at all).

 It's a generous design space, so although we have a couple of 
 ideas let's hear others first.


 Thanks,

 Andrei
Use an output range. It's the generic D approach, and what we already do for the string functions such as std.string.translate: http://dlang.org/phobos/std_string.html#.translate (look down for the output range overloads). Anything "allocator" related should be carried by the output range itself. The function itself should not care nor know about any of that.
Dec 05 2013
next sibling parent reply Jacob Carlborg <doob me.com> writes:
On 2013-12-05 09:09, monarch_dodra wrote:

 Use an output range. It's the generic D approach, and what we already do
 for the string functions such as std.string.translate:
 http://dlang.org/phobos/std_string.html#.translate
 (look down for the output range overloads).

 Anything "allocator" related should be carried by the output range
 itself. The function itself should not care nor know about any of that.
In general case, what would you suggest for functions not operating on ranges? -- /Jacob Carlborg
Dec 05 2013
parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Thursday, 5 December 2013 at 08:45:08 UTC, Jacob Carlborg 
wrote:
 On 2013-12-05 09:09, monarch_dodra wrote:

 Use an output range. It's the generic D approach, and what we 
 already do
 for the string functions such as std.string.translate:
 http://dlang.org/phobos/std_string.html#.translate
 (look down for the output range overloads).

 Anything "allocator" related should be carried by the output 
 range
 itself. The function itself should not care nor know about any 
 of that.
In general case, what would you suggest for functions not operating on ranges?
How do you mean? As in functions that only output a "single item"?
Dec 05 2013
next sibling parent reply Jacob Carlborg <doob me.com> writes:
On 2013-12-05 09:52, monarch_dodra wrote:

 How do you mean? As in functions that only output a "single item"?
Yes. -- /Jacob Carlborg
Dec 05 2013
parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Thursday, 5 December 2013 at 08:59:08 UTC, Jacob Carlborg 
wrote:
 On 2013-12-05 09:52, monarch_dodra wrote:

 How do you mean? As in functions that only output a "single 
 item"?
Yes.
I'd say simply with pass by ref, where the caller for puts the object on the stack (or wherever it wishes). If the object needs to further allocate, the said object itself should know how to it. In the use case where you *must* have a "foo(ref T* o)"-style signature, I'm not sure.
Dec 05 2013
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/5/13 12:52 AM, monarch_dodra wrote:
 On Thursday, 5 December 2013 at 08:45:08 UTC, Jacob Carlborg wrote:
 On 2013-12-05 09:09, monarch_dodra wrote:

 Use an output range. It's the generic D approach, and what we already do
 for the string functions such as std.string.translate:
 http://dlang.org/phobos/std_string.html#.translate
 (look down for the output range overloads).

 Anything "allocator" related should be carried by the output range
 itself. The function itself should not care nor know about any of that.
In general case, what would you suggest for functions not operating on ranges?
How do you mean? As in functions that only output a "single item"?
Returns a non-linear data structure such as a hash table. Andrei
Dec 05 2013
parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Thursday, 5 December 2013 at 15:00:07 UTC, Andrei Alexandrescu 
wrote:
 On 12/5/13 12:52 AM, monarch_dodra wrote:
 On Thursday, 5 December 2013 at 08:45:08 UTC, Jacob Carlborg 
 wrote:
 On 2013-12-05 09:09, monarch_dodra wrote:

 Use an output range. It's the generic D approach, and what 
 we already do
 for the string functions such as std.string.translate:
 http://dlang.org/phobos/std_string.html#.translate
 (look down for the output range overloads).

 Anything "allocator" related should be carried by the output 
 range
 itself. The function itself should not care nor know about 
 any of that.
In general case, what would you suggest for functions not operating on ranges?
How do you mean? As in functions that only output a "single item"?
Returns a non-linear data structure such as a hash table. Andrei
Output range! :) Output range interface makes no linearity requirements. Just that: "out.put(this)" compiles.
Dec 05 2013
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/5/13 8:19 AM, monarch_dodra wrote:
 On Thursday, 5 December 2013 at 15:00:07 UTC, Andrei Alexandrescu wrote:
 Andrei
Output range! :) Output range interface makes no linearity requirements. Just that: "out.put(this)" compiles.
Hrm, construction of a hash table is linearizable so bad example on my part. But I'm talking about general structured data such as objects with allocated fields and connections to other objects etc. etc. Andrei
Dec 05 2013
next sibling parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Thursday, 5 December 2013 at 16:46:52 UTC, Andrei Alexandrescu 
wrote:
 On 12/5/13 8:19 AM, monarch_dodra wrote:
 On Thursday, 5 December 2013 at 15:00:07 UTC, Andrei 
 Alexandrescu wrote:
 Andrei
Output range! :) Output range interface makes no linearity requirements. Just that: "out.put(this)" compiles.
Hrm, construction of a hash table is linearizable so bad example on my part. But I'm talking about general structured data such as objects with allocated fields and connections to other objects etc. etc. Andrei
Say, something like a graph? At that point, I'd say you'd have to pass an "allocating scheme" to the function, so an allocator, yes. Depending on the data being generated, the constructed item could carry the allocator itself. For example: auto newNode = myNode.GenerateNeighbor(); In But I think that'd be a special case situation. For everything else, output range is an easy and intuitive, and fits well with the rest of phobos. We'd want (IMHO) to integrate the allocators directly inside the output ranges.
Dec 05 2013
next sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Thursday, 5 December 2013 at 17:06:13 UTC, monarch_dodra wrote:
 On Thursday, 5 December 2013 at 16:46:52 UTC, Andrei 
 Alexandrescu wrote:
 On 12/5/13 8:19 AM, monarch_dodra wrote:
 On Thursday, 5 December 2013 at 15:00:07 UTC, Andrei 
 Alexandrescu wrote:
 Andrei
Output range! :) Output range interface makes no linearity requirements. Just that: "out.put(this)" compiles.
Hrm, construction of a hash table is linearizable so bad example on my part. But I'm talking about general structured data such as objects with allocated fields and connections to other objects etc. etc. Andrei
 In But I think that'd be a special case situation. For 
 everything else, output range is an easy and intuitive, and 
 fits well with the rest of phobos. We'd want (IMHO) to 
 integrate the allocators directly inside the output ranges.
I really need to re-read myself before posting, sorry :/ But I think that'd be a special case situation. For everything else, output ranges are easy and intuitive, and fit well with the rest of phobos. We'd want (IMHO) to integrate allocation directly inside output ranges.
Dec 05 2013
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/5/13 9:06 AM, monarch_dodra wrote:
 On Thursday, 5 December 2013 at 16:46:52 UTC, Andrei Alexandrescu wrote:
 On 12/5/13 8:19 AM, monarch_dodra wrote:
 On Thursday, 5 December 2013 at 15:00:07 UTC, Andrei Alexandrescu wrote:
 Andrei
Output range! :) Output range interface makes no linearity requirements. Just that: "out.put(this)" compiles.
Hrm, construction of a hash table is linearizable so bad example on my part. But I'm talking about general structured data such as objects with allocated fields and connections to other objects etc. etc. Andrei
Say, something like a graph? At that point, I'd say you'd have to pass an "allocating scheme" to the function, so an allocator, yes. Depending on the data being generated, the constructed item could carry the allocator itself. For example: auto newNode = myNode.GenerateNeighbor(); In But I think that'd be a special case situation. For everything else, output range is an easy and intuitive, and fits well with the rest of phobos. We'd want (IMHO) to integrate the allocators directly inside the output ranges.
Trees and graphs are not special cases. They're bread and butter objects with fields that are in turn allocated etc. Consider how difficult it would be (for both the implementer and the user) to fill via an output range an object (class or struct) that has a few fields that need allocation (such as strings and arrays). It becomes a mini-serialization project. We can't realistically propose that as a way to allow users to control memory allocation. Andrei
Dec 05 2013
parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Thursday, 5 December 2013 at 18:34:40 UTC, Andrei Alexandrescu 
wrote:
 Trees and graphs are not special cases. They're bread and 
 butter objects with fields that are in turn allocated etc.
Yes, and they aren't really linear containers either, but that doesn't mean we throw the input range concept out the window. The graph itself could carry the allocator, and just the same you have a function "getNeighbors" that returns an input range of a node's neighboring nodes, the graph could also give a collection of different ouput ranges that takes care of allocation. I'm just saying it's not something I'd like to see that *functions* take allocators as arguments. I think that should be abstracted by the containers/ranges themselves, in such a way that the functions only have to use things like "pushBack" (eg: std::back_inserter).
 Consider how difficult it would be (for both the implementer 
 and the user) to fill via an output range an object (class or 
 struct) that has a few fields that need allocation (such as 
 strings and arrays). It becomes a mini-serialization project. 
 We can't realistically propose that as a way to allow users to 
 control memory allocation.
I'm out of my league on this one.
Dec 05 2013
prev sibling next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Thu, Dec 05, 2013 at 08:46:52AM -0800, Andrei Alexandrescu wrote:
 On 12/5/13 8:19 AM, monarch_dodra wrote:
On Thursday, 5 December 2013 at 15:00:07 UTC, Andrei Alexandrescu wrote:
Andrei
Output range! :) Output range interface makes no linearity requirements. Just that: "out.put(this)" compiles.
Hrm, construction of a hash table is linearizable so bad example on my part. But I'm talking about general structured data such as objects with allocated fields and connections to other objects etc. etc.
[...] I got your point from your previous post. It made me wonder how something like, say, a directed graph could be constructed in a way such that the caller gets to control how memory is allocated. My first thought was to use an abstract factory object that exposes an API that allowed construction of nodes and edges. The function would take this API as argument, and the caller provides the actual implementation. However, on further thought, this doesn't address the case when the function needs to do something opaque to the API, such as creating a derived class of a graph node (assuming the API has some kind of method that allocates and creates nodes). Ultimately, it seems that an allocator is the only way that doesn't make the caller/callee interface extremely ugly and leaky. T -- People tell me I'm stubborn, but I refuse to accept it!
Dec 05 2013
prev sibling next sibling parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
05-Dec-2013 20:46, Andrei Alexandrescu пишет:
 On 12/5/13 8:19 AM, monarch_dodra wrote:
 On Thursday, 5 December 2013 at 15:00:07 UTC, Andrei Alexandrescu wrote:
 Andrei
Output range! :) Output range interface makes no linearity requirements. Just that: "out.put(this)" compiles.
Hrm, construction of a hash table is linearizable so bad example on my part. But I'm talking about general structured data such as objects with allocated fields and connections to other objects etc. etc.
Pass desired container type that follows some implicit protocol such as isGraph!T. Then container type defines allocation scheme (=some container specific default). As an extended version allow passing reference to an allocator to use with that container type. -- Dmitry Olshansky
Dec 05 2013
prev sibling parent reply Michel Fortin <michel.fortin michelf.ca> writes:
On 2013-12-05 16:46:52 +0000, Andrei Alexandrescu 
<SeeWebsiteForEmail erdani.org> said:

 On 12/5/13 8:19 AM, monarch_dodra wrote:
 Output range! :)
 
 Output range interface makes no linearity requirements. Just that:
 "out.put(this)" compiles.
Hrm, construction of a hash table is linearizable so bad example on my part. But I'm talking about general structured data such as objects with allocated fields and connections to other objects etc. etc.
You have to admit that a "bump the pointer" allocator is pretty much the same thing as an output range that fills a preexisting array. So here's an interesting idea: perhaps typed allocators should *be* output ranges. The difference is that if you "put" something on the allocator, it copies/moves it to the allocator's heap and returns you a pointer. While if you "put" something on a generic output range, don't expect any pointer out of it. Some functions, like buildPath, would only require an output range. Others will need a more complete allocator, that's those functions that want to refer back to elements they've "put" on the allocator's heap. -- Michel Fortin michel.fortin michelf.ca http://michelf.ca
Dec 07 2013
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/7/13 5:13 AM, Michel Fortin wrote:
 On 2013-12-05 16:46:52 +0000, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> said:

 On 12/5/13 8:19 AM, monarch_dodra wrote:
 Output range! :)

 Output range interface makes no linearity requirements. Just that:
 "out.put(this)" compiles.
Hrm, construction of a hash table is linearizable so bad example on my part. But I'm talking about general structured data such as objects with allocated fields and connections to other objects etc. etc.
You have to admit that a "bump the pointer" allocator is pretty much the same thing as an output range that fills a preexisting array.
Only of the output range is untyped. An allocator traffics in untyped chunks; an output range usually has an element type.
 So here's an interesting idea: perhaps typed allocators should *be*
 output ranges. The difference is that if you "put" something on the
 allocator, it copies/moves it to the allocator's heap and returns you a
 pointer. While if you "put" something on a generic output range, don't
 expect any pointer out of it.

 Some functions, like buildPath, would only require an output range.
 Others will need a more complete allocator, that's those functions that
 want to refer back to elements they've "put" on the allocator's heap.
I don't think that would work. Andrei
Dec 07 2013
parent reply Michel Fortin <michel.fortin michelf.ca> writes:
On 2013-12-07 16:08:18 +0000, Andrei Alexandrescu 
<SeeWebsiteForEmail erdani.org> said:

 On 12/7/13 5:13 AM, Michel Fortin wrote:
 You have to admit that a "bump the pointer" allocator is pretty much the
 same thing as an output range that fills a preexisting array.
Only of the output range is untyped. An allocator traffics in untyped chunks; an output range usually has an element type.
If I remember well, you said before that you may also design "typed allocators" that'd work at a layer above untyped allocators. That's what I was referring to, although I wasn't very clear (the words "typed allocator" only appeared after the paragraph quoted above). Anyway, here's another thing to consider in the Output Range vs. Allocator debate: allocators can be faster than output ranges because you can tell the allocator in advance how much data you need. For instance, if you're joining multiple strings together you can quickly calculate the final length, allocate that, write to allocated memory and return the result. In fact, that's exactly what buildPath currently does when allocating from the GC. With an output range that appends to a string the string needs to constantly grow to accommodate new content, with no insight as to the final length. The way to fix that with an output range would be to have have a "reserve" function telling the range "prepare yourself to receive that much data", which may or may not do something depending on the kind of output range it is. There's no such function in the definition of an output range right now. -- Michel Fortin michel.fortin michelf.ca http://michelf.ca
Dec 07 2013
parent Marco Leise <Marco.Leise gmx.de> writes:
Am Sat, 7 Dec 2013 13:27:07 -0500
schrieb Michel Fortin <michel.fortin michelf.ca>:

 [=E2=80=A6] The way to fix that with an output range would be to have=20
 have a "reserve" function telling the range "prepare yourself to=20
 receive that much data", which may or may not do something depending on=20
 the kind of output range it is.
This could even preallocate blocks on a filesystem for file record based output ranges. (In order to avoid file fragmentation on mechanical disks.) --=20 Marco
Dec 07 2013
prev sibling parent reply "Brad Anderson" <eco gnuk.net> writes:
On Thursday, 5 December 2013 at 08:09:55 UTC, monarch_dodra wrote:
 On Wednesday, 4 December 2013 at 23:14:48 UTC, Andrei 
 Alexandrescu wrote:
 Hello,


 Walter and I were talking about eliminating the surreptitious 
 allocations in buildPath:

 http://dlang.org/phobos/std_path.html#.buildPath

 We'd need to keep the existing version working, so we're 
 looking at adding one or more new overloads. We're looking at 
 giving the user the option to control any needed memory 
 allocation (or even arrange things such that there's no memory 
 allocated at all).

 It's a generous design space, so although we have a couple of 
 ideas let's hear others first.


 Thanks,

 Andrei
Use an output range. It's the generic D approach, and what we already do for the string functions such as std.string.translate: http://dlang.org/phobos/std_string.html#.translate (look down for the output range overloads). Anything "allocator" related should be carried by the output range itself. The function itself should not care nor know about any of that.
And thanks to your improvements[1] to put() output ranges should actually be much more usable than they ever were before. I've mentioned this a few times but I tried to add an output range overload of toUpper and toLower but immediately encountered problems with appending dchars to char arrays. Your recently merged improvements to put() appear to have addressed that problem and many others and I'll soon have another go at adding these overloads now that that change is in place so thanks for doing the hard work. Before this got merged I don't even think output ranges could be easily used for this improvement to buildPath so it got merged at a very convenient time. (my memory is a bit poor but if I'm remembering correctly appender worked because it had done its own handling of narrow strings but you couldn't just use a static or dynamic narrow string array as an output range) 1. https://github.com/D-Programming-Language/phobos/pull/1569
Dec 05 2013
parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Thursday, 5 December 2013 at 20:47:32 UTC, Brad Anderson wrote:
 And thanks to your improvements[1] to put() output ranges 
 should actually be much more usable than they ever were before. 
 I've mentioned this a few times but I tried to add an output 
 range overload of toUpper and toLower but immediately 
 encountered problems with appending dchars to char arrays.  
 Your recently merged improvements to put() appear to have 
 addressed that problem and many others and I'll soon have 
 another go at adding these overloads now that that change is in 
 place so thanks for doing the hard work.

 Before this got merged I don't even think output ranges could 
 be easily used for this improvement to buildPath so it got 
 merged at a very convenient time.

 (my memory is a bit poor but if I'm remembering correctly 
 appender worked because it had done its own handling of narrow 
 strings but you couldn't just use a static or dynamic narrow 
 string array as an output range)

 1. https://github.com/D-Programming-Language/phobos/pull/1569
Yes, appender did its own trans-coding, which helped the situation, but it made things like output delegates absolutely useless. My next step was to *remove* the on the fly trancoding in appender, to rely only "put", directly, but I fear that would cause un-necessary breakge, due to UFCS not triggering if the member function exists: In the sense that put(appender!string(), myDstring); //Yes appender!string().put(myDstring); //Nope
Dec 05 2013
prev sibling parent reply "inout" <inout gmail.com> writes:
On Wednesday, 4 December 2013 at 23:14:48 UTC, Andrei 
Alexandrescu wrote:
 Hello,


 Walter and I were talking about eliminating the surreptitious 
 allocations in buildPath:

 http://dlang.org/phobos/std_path.html#.buildPath

 We'd need to keep the existing version working, so we're 
 looking at adding one or more new overloads. We're looking at 
 giving the user the option to control any needed memory 
 allocation (or even arrange things such that there's no memory 
 allocated at all).

 It's a generous design space, so although we have a couple of 
 ideas let's hear others first.


 Thanks,

 Andrei
My approach in cases like that used to be to pass an optional char[] buffer = null as last argument (it doesn't work as nice in variadic functions though): // constructs the result in a buffer if one is passed until there is no more space left, in which case it reallocates the buffer char[] buildPath(const(char)[] path1, const(char)[] path2, char[] buffer = null) { Appender!(char) appender = useBuffer(buffer); ... }
Dec 05 2013
parent "Brad Anderson" <eco gnuk.net> writes:
On Thursday, 5 December 2013 at 17:30:37 UTC, inout wrote:
 My approach in cases like that used to be to pass an optional 
 char[] buffer = null as last argument (it doesn't work as nice 
 in variadic functions though):

 // constructs the result in a buffer if one is passed until 
 there is no more space left, in which case it reallocates the 
 buffer
 char[] buildPath(const(char)[] path1, const(char)[] path2, 
 char[] buffer = null) {
   Appender!(char) appender = useBuffer(buffer);
   ...
 }
The nice thing about output ranges instead of this approach is the allocation strategy is left up to the caller rather than the function. I think generalized SSO (a small static buffer that can fall back to a dynamic allocation) will become a very common idiom as more and more of phobos accepts output ranges.
Dec 05 2013