www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Ranges require GC?

reply "Frustrated" <c1514843 drdrb.com> writes:
I assume that ranges require the GC, is this true?
Dec 10 2013
parent reply "Adam D. Ruppe" <destructionator gmail.com> writes:
On Tuesday, 10 December 2013 at 18:54:54 UTC, Frustrated wrote:
 I assume that ranges require the GC, is this true?
No, in fact, most ranges don't allocate at all.
Dec 10 2013
parent reply Marco Leise <Marco.Leise gmx.de> writes:
Am Tue, 10 Dec 2013 19:55:20 +0100
schrieb "Adam D. Ruppe" <destructionator gmail.com>:

 On Tuesday, 10 December 2013 at 18:54:54 UTC, Frustrated wrote:
 I assume that ranges require the GC, is this true?
No, in fact, most ranges don't allocate at all.
"range" is just a concept and not a concrete type. Functions that work on ranges identify them by specific calls that can be made on them. (e.g. front, popFront(), length, etc.). This is commonly known as duck-typing. And allows much anything to be a range: Classes, structs, built-in arrays. D objects and dynamic arrays are typically GC managed. Most ranges returned from Phobos are implemented as structs though and don't need a GC. If you write something like: [1,2,3].map!(a => a+1)() then you are using a dynamic array ([1,2,3]) that will live in the GC heap. "map" will then just return a range (implemented as a struct). One has to understand that no memory will be allocated to hold the result of the map process. In fact where possible, Phobos returns lazily evaluated ranges that only calculate the next item when you ask for it (using .front and .popFront() on it). -- Marco
Dec 10 2013
parent reply "Frustrated" <c1514843 drdrb.com> writes:
On Tuesday, 10 December 2013 at 21:20:59 UTC, Marco Leise wrote:
 Am Tue, 10 Dec 2013 19:55:20 +0100
 schrieb "Adam D. Ruppe" <destructionator gmail.com>:

 On Tuesday, 10 December 2013 at 18:54:54 UTC, Frustrated wrote:
 I assume that ranges require the GC, is this true?
No, in fact, most ranges don't allocate at all.
"range" is just a concept and not a concrete type. Functions that work on ranges identify them by specific calls that can be made on them. (e.g. front, popFront(), length, etc.). This is commonly known as duck-typing. And allows much anything to be a range: Classes, structs, built-in arrays. D objects and dynamic arrays are typically GC managed. Most ranges returned from Phobos are implemented as structs though and don't need a GC. If you write something like: [1,2,3].map!(a => a+1)() then you are using a dynamic array ([1,2,3]) that will live in the GC heap. "map" will then just return a range (implemented as a struct). One has to understand that no memory will be allocated to hold the result of the map process. In fact where possible, Phobos returns lazily evaluated ranges that only calculate the next item when you ask for it (using .front and .popFront() on it).
But surely memory gets allocated in some way? In Programming in D: "For example filter(), which chooses elements that are greater than 10 in the following code, actually returns a range object, not an array:" But if filter is a range and returns an object then how is that object allocated?
Dec 10 2013
parent reply "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Wednesday, December 11, 2013 03:09:52 Frustrated wrote:
 But surely memory gets allocated in some way?
 
 In Programming in D:
 
 "For example filter(), which
 chooses elements that are greater than 10 in the following code,
 actually returns a range
 object, not an array:"
 
 But if filter is a range and returns an object then how is that
 object allocated?
It's on the stack. filter returns a struct whose only member is the range that was passed to it. The lambda that you pass to filter might be allocated on the heap under some circumstances, but that's the only risk of heap allocation with filter, and if you use a function rather than a lambda literal or a delegate, then you definitely don't get any heap allocation (and I don't think that it's even the case that you necessarily get a heap allocation with a lambda). Most ranges in Phobos are very lightweight, because they just wrap another range and maybe add a member variable or two to handle what they do (and many don't even need that). And if the optimizer does a decent job, then most of the wrappers even get optimized away, causing very little overhead at all (though I'm sure that dmd can be improved in that regard). Whether any particular range allocates anything on the heap depends on the range, but it's likely to be very rare that they will - particularly in Phobos. - Jonathan M Davis
Dec 10 2013
parent reply "Frustrated" <c1514843 drdrb.com> writes:
On Wednesday, 11 December 2013 at 02:37:32 UTC, Jonathan M Davis 
wrote:
 On Wednesday, December 11, 2013 03:09:52 Frustrated wrote:
 But surely memory gets allocated in some way?
 
 In Programming in D:
 
 "For example filter(), which
 chooses elements that are greater than 10 in the following 
 code,
 actually returns a range
 object, not an array:"
 
 But if filter is a range and returns an object then how is that
 object allocated?
It's on the stack. filter returns a struct whose only member is the range that was passed to it. The lambda that you pass to filter might be allocated on the heap under some circumstances, but that's the only risk of heap allocation with filter, and if you use a function rather than a lambda literal or a delegate, then you definitely don't get any heap allocation (and I don't think that it's even the case that you necessarily get a heap allocation with a lambda). Most ranges in Phobos are very lightweight, because they just wrap another range and maybe add a member variable or two to handle what they do (and many don't even need that). And if the optimizer does a decent job, then most of the wrappers even get optimized away, causing very little overhead at all (though I'm sure that dmd can be improved in that regard). Whether any particular range allocates anything on the heap depends on the range, but it's likely to be very rare that they will - particularly in Phobos. - Jonathan M Davis
I'm trying to avoid the GC so knowing whether or not ranges will use the heap is extremely important. I guess that is where the nogc attribute that everyone talks about would come in very handy.
Dec 10 2013
parent Marco Leise <Marco.Leise gmx.de> writes:
Am Wed, 11 Dec 2013 08:20:19 +0100
schrieb "Frustrated" <c1514843 drdrb.com>:

 On Wednesday, 11 December 2013 at 02:37:32 UTC, Jonathan M Davis 
 wrote:
 On Wednesday, December 11, 2013 03:09:52 Frustrated wrote:
 But surely memory gets allocated in some way?
 
 In Programming in D:
 
 "For example filter(), which
 chooses elements that are greater than 10 in the following 
 code,
 actually returns a range
 object, not an array:"
 
 But if filter is a range and returns an object then how is that
 object allocated?
That's just a wording issue. It means object in the wider sense, not instance of a class.
 I'm trying to avoid the GC so knowing whether or not ranges will 
 use the heap is extremely important. I guess that is where the 
  nogc attribute that everyone talks about would come in very 
 handy.
Correct. -- Marco
Dec 11 2013