digitalmars.D - Caching in computing ranges
- Tomek =?UTF-8?B?U293acWEc2tp?= (14/14) Oct 09 2010 I've been having fun with ranges lately. While nesting computing ranges ...
- Pelle (6/18) Oct 09 2010 How about never having caches and if you need them, you can get a
- Peter Alexander (4/9) Oct 09 2010 I agree with this. Caching should not be a default.
- Tomek =?UTF-8?B?U293acWEc2tp?= (9/21) Oct 09 2010 std.range.Sequence also caches. I swear I saw Zip do it too, but looking...
- Peter Alexander (4/5) Oct 09 2010 I believe you have been accepted as a trusted commiter by some people
- bearophile (4/7) Oct 09 2010 Right. While DMD is currently NOT managed as a true Open Source project ...
- Andrei Alexandrescu (6/25) Oct 09 2010 Thanks for offering. Patches or simple snippets meant to replace
- Andrei Alexandrescu (3/13) Oct 09 2010 It's the only one I can remember.
- Tomek =?UTF-8?B?U293acWEc2tp?= (6/30) Oct 09 2010 Plus, computations are done in popFront(). Then skippers like Stride com...
- Andrei Alexandrescu (6/18) Oct 09 2010 I think it's a good idea. In fact let's eliminate caching altogether; it...
- dsimcha (10/30) Oct 09 2010 ranges deeper
- Andrei Alexandrescu (13/18) Oct 09 2010 Cached will be quite a story in and of itself. I can tell you for sure
- Lars T. Kyllingstad (3/27) Oct 11 2010 A PushBack!Range that allows 'un-popping' elements could also be useful.
- Peter Alexander (2/7) Oct 09 2010 Yep, kill it.
I've been having fun with ranges lately. While nesting computing ranges I noticed only the outermost range's cache is necessary; there's no way of accessing front() of ranges deeper in the expression twice because they are sealed by the outermost range. Example: map!"a._0 + a._1"( // caches, front() may be called twice zip( // oh, trumpet: front() is called only to compute outer map's cache map!"a*a"([2, 4, 5, 6]), // oh, trumpet take(sequence!"a._0 + n * a._1"(1, 2), 4) // oh, trumpet ) ); Eliminating superfluous caches, among other benefits, allows inlining the (usually cheap) front()s. One way to do it is to parametrize computing ranges with an enum Cached.(yes|no). What you think? -- Tomek
Oct 09 2010
On 10/09/2010 09:38 PM, Tomek Sowiński wrote:I've been having fun with ranges lately. While nesting computing ranges I noticed only the outermost range's cache is necessary; there's no way of accessing front() of ranges deeper in the expression twice because they are sealed by the outermost range. Example: map!"a._0 + a._1"( // caches, front() may be called twice zip( // oh, trumpet: front() is called only to compute outer map's cache map!"a*a"([2, 4, 5, 6]), // oh, trumpet take(sequence!"a._0 + n * a._1"(1, 2), 4) // oh, trumpet ) ); Eliminating superfluous caches, among other benefits, allows inlining the (usually cheap) front()s. One way to do it is to parametrize computing ranges with an enum Cached.(yes|no). What you think?How about never having caches and if you need them, you can get a cached(map(..etc..))? I do not understand where the notion that ranges should have caches come from. It destroys the possibility for using const and complicates the writing of them.
Oct 09 2010
On 9/10/10 8:58 PM, Pelle wrote:How about never having caches and if you need them, you can get a cached(map(..etc..))? I do not understand where the notion that ranges should have caches come from. It destroys the possibility for using const and complicates the writing of them.I agree with this. Caching should not be a default. As it stands, I know that std.algorithm.Map uses a cache, I haven't checked any others.
Oct 09 2010
Peter Alexander napisał:On 9/10/10 8:58 PM, Pelle wrote:std.range.Sequence also caches. I swear I saw Zip do it too, but looking at the code now, I see no cache. By the way, I've been reading Phobos quite intensively lately and I'm willing to spend some time to make the change Pelle was talking about (remove caching, add the Cached higher- order range). How can I contribute that to Phobos? -- TomekHow about never having caches and if you need them, you can get a cached(map(..etc..))? I do not understand where the notion that ranges should have caches come from. It destroys the possibility for using const and complicates the writing of them.I agree with this. Caching should not be a default. As it stands, I know that std.algorithm.Map uses a cache, I haven't checked any others.
Oct 09 2010
On 9/10/10 10:06 PM, Tomek Sowiński wrote:How can I contribute that to Phobos?I believe you have been accepted as a trusted commiter by some people (Walter and Andrei?). Most people appear to earn trust by writing a high quality library.
Oct 09 2010
Peter Alexander:I believe you have been accepted as a trusted commiter by some people (Walter and Andrei?). Most people appear to earn trust by writing a high quality library.Right. While DMD is currently NOT managed as a true Open Source project (and this is very bad for the future and development of the D language, and will need to be eventually fixed if D wants a bit more success), Phobos2 is becoming open source enough, there are several good and gentle people working on Phobos2, Andrei is gentle and accepts the code he receives, etc. So Phobos2 may avoid the fate of Phobos1 (where the frustration of people unable to push patches upstream has lead to the creation of Tango). Becoming more Open Source (where people can patch the code written by others) can't guarantee a future to D, but the opposite is worse. Walter is now accepting more patches and suggestions from Don, so the situation is improving a bit regarding the compiler too, so I am happy and hopeful :-) Bye, bearophile
Oct 09 2010
On 10/9/10 16:06 CDT, Tomek Sowiński wrote:Peter Alexander napisał:Thanks for offering. Patches or simple snippets meant to replace well-defined parts of existing code should be fine. But in this case (i.e. caching) where the replacement is trivial, a bug report would be sufficient and most appreciated. AndreiOn 9/10/10 8:58 PM, Pelle wrote:std.range.Sequence also caches. I swear I saw Zip do it too, but looking at the code now, I see no cache. By the way, I've been reading Phobos quite intensively lately and I'm willing to spend some time to make the change Pelle was talking about (remove caching, add the Cached higher- order range). How can I contribute that to Phobos?How about never having caches and if you need them, you can get a cached(map(..etc..))? I do not understand where the notion that ranges should have caches come from. It destroys the possibility for using const and complicates the writing of them.I agree with this. Caching should not be a default. As it stands, I know that std.algorithm.Map uses a cache, I haven't checked any others.
Oct 09 2010
On 10/9/10 15:12 CDT, Peter Alexander wrote:On 9/10/10 8:58 PM, Pelle wrote:It's the only one I can remember. AndreiHow about never having caches and if you need them, you can get a cached(map(..etc..))? I do not understand where the notion that ranges should have caches come from. It destroys the possibility for using const and complicates the writing of them.I agree with this. Caching should not be a default. As it stands, I know that std.algorithm.Map uses a cache, I haven't checked any others.
Oct 09 2010
Pelle napisał:On 10/09/2010 09:38 PM, Tomek Sowiński wrote:That's an excellent idea.I've been having fun with ranges lately. While nesting computing ranges I noticed only the outermost range's cache is necessary; there's no way of accessing front() of ranges deeper in the expression twice because they are sealed by the outermost range. Example: map!"a._0 + a._1"( // caches, front() may be called twice zip( // oh, trumpet: front() is called only to compute outer map's cache map!"a*a"([2, 4, 5, 6]), // oh, trumpet take(sequence!"a._0 + n * a._1"(1, 2), 4) // oh, trumpet ) ); Eliminating superfluous caches, among other benefits, allows inlining the (usually cheap) front()s. One way to do it is to parametrize computing ranges with an enum Cached.(yes|no). What you think?How about never having caches and if you need them, you can get a cached(map(..etc..))?I do not understand where the notion that ranges should have caches come from. It destroys the possibility for using const and complicates the writing of them.Plus, computations are done in popFront(). Then skippers like Stride compute many values in vain. -- Tomek
Oct 09 2010
On 10/9/10 14:38 CDT, Tomek Sowiński wrote:I've been having fun with ranges lately. While nesting computing ranges I noticed only the outermost range's cache is necessary; there's no way of accessing front() of ranges deeper in the expression twice because they are sealed by the outermost range. Example: map!"a._0 + a._1"( // caches, front() may be called twice zip( // oh, trumpet: front() is called only to compute outer map's cache map!"a*a"([2, 4, 5, 6]), // oh, trumpet take(sequence!"a._0 + n * a._1"(1, 2), 4) // oh, trumpet ) ); Eliminating superfluous caches, among other benefits, allows inlining the (usually cheap) front()s. One way to do it is to parametrize computing ranges with an enum Cached.(yes|no). What you think?I think it's a good idea. In fact let's eliminate caching altogether; it does not happen for the random access operator anyway and I think it's fair to simply evaluate the function whenever an element is accessed. Whaddaya think? Andrei
Oct 09 2010
== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s articleOn 10/9/10 14:38 CDT, Tomek Sowiński wrote:noticed only theI've been having fun with ranges lately. While nesting computing ranges Iranges deeperoutermost range's cache is necessary; there's no way of accessing front() of(usually cheap)in the expression twice because they are sealed by the outermost range. Example: map!"a._0 + a._1"( // caches, front() may be called twice zip( // oh, trumpet: front() is called only to compute outer map's cache map!"a*a"([2, 4, 5, 6]), // oh, trumpet take(sequence!"a._0 + n * a._1"(1, 2), 4) // oh, trumpet ) ); Eliminating superfluous caches, among other benefits, allows inlining theCached.(yes|no).front()s. One way to do it is to parametrize computing ranges with an enumVote++. When I added bidirectional support for map(), I felt like any solution for doing bidirectional caching was going to suck. I considered just eliminating it, but left it because at the time I was more interested in just getting bidirectional/random access working than worrying about the cache issue. IMHO the only range that should be cached is a Cached higher order range.What you think?I think it's a good idea. In fact let's eliminate caching altogether; it does not happen for the random access operator anyway and I think it's fair to simply evaluate the function whenever an element is accessed. Whaddaya think? Andrei
Oct 09 2010
On 10/9/10 18:20 CDT, dsimcha wrote:Vote++. When I added bidirectional support for map(), I felt like any solution for doing bidirectional caching was going to suck. I considered just eliminating it, but left it because at the time I was more interested in just getting bidirectional/random access working than worrying about the cache issue. IMHO the only range that should be cached is a Cached higher order range.Cached will be quite a story in and of itself. I can tell you for sure we need two related abstractions in std.range: 1. Lookback!Range provides a history that allows the range to look back up to n items: auto r = lookback(file.byLine(), 20); ... r.lookback(3); // three lines before the current 2. Lookahead!Range similarly allows looking ahead: auto r = lookahead(file.byLine(), 20); ... r.lookahead(3); // three lines after the current Andrei
Oct 09 2010
On Sat, 09 Oct 2010 18:43:54 -0500, Andrei Alexandrescu wrote:On 10/9/10 18:20 CDT, dsimcha wrote:A PushBack!Range that allows 'un-popping' elements could also be useful. -LarsVote++. When I added bidirectional support for map(), I felt like any solution for doing bidirectional caching was going to suck. I considered just eliminating it, but left it because at the time I was more interested in just getting bidirectional/random access working than worrying about the cache issue. IMHO the only range that should be cached is a Cached higher order range.Cached will be quite a story in and of itself. I can tell you for sure we need two related abstractions in std.range: 1. Lookback!Range provides a history that allows the range to look back up to n items: auto r = lookback(file.byLine(), 20); ... r.lookback(3); // three lines before the current 2. Lookahead!Range similarly allows looking ahead: auto r = lookahead(file.byLine(), 20); ... r.lookahead(3); // three lines after the current Andrei
Oct 11 2010
On 9/10/10 11:40 PM, Andrei Alexandrescu wrote:I think it's a good idea. In fact let's eliminate caching altogether; it does not happen for the random access operator anyway and I think it's fair to simply evaluate the function whenever an element is accessed. Whaddaya think? AndreiYep, kill it.
Oct 09 2010