digitalmars.D - Interesting Memory Optimization
- Kevin (11/11) Mar 15 2012 This is in no way D specific but say you have two constant strings.
- Xinok (2/16) Mar 15 2012 I'm pretty sure this is called string pooling.
- =?UTF-8?B?QWxleCBSw7hubmUgUGV0ZXJzZW4=?= (4/21) Mar 15 2012 Right. Most compilers do it.
- Kevin (2/5) Mar 15 2012 Cool. You learn something every day.
- Peter Alexander (9/29) Mar 16 2012 My understanding is that string pooling just shares whole strings
- =?UTF-8?B?QWxleCBSw7hubmUgUGV0ZXJzZW4=?= (5/32) Mar 16 2012 I don't see any reason why c couldn't point to element number 3 of b,
- Kevin Cox (10/13) Mar 16 2012 have its length set to 3...
- Jakob Ovrum (3/22) Mar 16 2012 All compile-time generated strings (like literals) in D are
- Don Clugston (3/18) Mar 16 2012 Unfortunately string literals in D have an implicit \0 added beyond the
- H. S. Teoh (6/15) Mar 16 2012 More to the point, does dmd perform this optimization currently?
- Timon Gehr (5/18) Mar 16 2012 No.
- Xinok (19/30) Mar 16 2012 It actually does, but only identical strings. It doesn't seem to
- Xinok (18/51) Mar 16 2012 Captain obvious to the rescue, 'is' is false if the strings are
- Timon Gehr (22/76) Mar 16 2012 It can't because there must be a terminating zero byte. It does not do
- Xinok (3/24) Mar 16 2012 So while D does pool strings, it doesn't seem to optimize
- Adam D. Ruppe (4/6) Mar 16 2012 Don't forget that "123" is /not/ a substring of "123456"
- Peter Alexander (5/44) Mar 18 2012 Neither do I, but it's more work for the compiler, and even if
- Kevin Cox (6/7) Mar 18 2012 compiler does string pooling, it may not look for common suffixes.
- Steven Schveighoffer (15/25) Mar 19 2012 I have done this manually in the past. In an application that ran on a ...
- Derek (10/20) Mar 19 2012 Is the effort to do this really an issue with today's vast amounts of RA...
- Timon Gehr (3/20) Mar 19 2012 Using less memory means having less cache misses and therefore improved
- H. S. Teoh (11/36) Mar 19 2012 While the *total* amount of memory used may not matter so much, cache
- James Miller (19/25) Mar 19 2012 Gah, I hate this sentiment! It encourages lazy, poor design and
- H. S. Teoh (32/59) Mar 19 2012 Not to mention that this kind of fallacious attitude causes people to
- James Miller (31/43) Mar 19 2012 And whats more, developer productivity is not a function of the tools
This is in no way D specific but say you have two constant strings. const char[] a = "1234567890"; // and const char[] b = "67890"; You could lay out the memory inside of one another. IE: if a.ptr = 1 then b.ptr = 6. I'm not sure if this has been done and I don't think it would apply very often but it would be kinda cool. I thought of this because I wanted to pre-generate hex-representations of some numbers I realized I could use half the memory if I nested them. (At least I think it would be half). Kevin.
Mar 15 2012
On Friday, 16 March 2012 at 02:18:27 UTC, Kevin wrote:This is in no way D specific but say you have two constant strings. const char[] a = "1234567890"; // and const char[] b = "67890"; You could lay out the memory inside of one another. IE: if a.ptr = 1 then b.ptr = 6. I'm not sure if this has been done and I don't think it would apply very often but it would be kinda cool. I thought of this because I wanted to pre-generate hex-representations of some numbers I realized I could use half the memory if I nested them. (At least I think it would be half). Kevin.I'm pretty sure this is called string pooling.
Mar 15 2012
On 16-03-2012 03:31, Xinok wrote:On Friday, 16 March 2012 at 02:18:27 UTC, Kevin wrote:Right. Most compilers do it. -- - AlexThis is in no way D specific but say you have two constant strings. const char[] a = "1234567890"; // and const char[] b = "67890"; You could lay out the memory inside of one another. IE: if a.ptr = 1 then b.ptr = 6. I'm not sure if this has been done and I don't think it would apply very often but it would be kinda cool. I thought of this because I wanted to pre-generate hex-representations of some numbers I realized I could use half the memory if I nested them. (At least I think it would be half). Kevin.I'm pretty sure this is called string pooling.
Mar 15 2012
On 03/15/2012 10:35 PM, Alex Rønne Petersen wrote:On 16-03-2012 03:31, Xinok wrote:Cool. You learn something every day.I'm pretty sure this is called string pooling.Right. Most compilers do it.
Mar 15 2012
On Friday, 16 March 2012 at 02:31:47 UTC, Xinok wrote:On Friday, 16 March 2012 at 02:18:27 UTC, Kevin wrote:My understanding is that string pooling just shares whole strings rather than combining suffixes. e.g. const char[] a = "fubar"; const char[] b = "fubar"; // shared const char[] c = "bar"; // not shared at all Combining suffixes is obviously possible, but I'm not sure that string pooling implies suffix pooling.This is in no way D specific but say you have two constant strings. const char[] a = "1234567890"; // and const char[] b = "67890"; You could lay out the memory inside of one another. IE: if a.ptr = 1 then b.ptr = 6. I'm not sure if this has been done and I don't think it would apply very often but it would be kinda cool. I thought of this because I wanted to pre-generate hex-representations of some numbers I realized I could use half the memory if I nested them. (At least I think it would be half). Kevin.I'm pretty sure this is called string pooling.
Mar 16 2012
On 16-03-2012 12:32, Peter Alexander wrote:On Friday, 16 March 2012 at 02:31:47 UTC, Xinok wrote:I don't see any reason why c couldn't point to element number 3 of b, and have its length set to 3... -- - AlexOn Friday, 16 March 2012 at 02:18:27 UTC, Kevin wrote:My understanding is that string pooling just shares whole strings rather than combining suffixes. e.g. const char[] a = "fubar"; const char[] b = "fubar"; // shared const char[] c = "bar"; // not shared at all Combining suffixes is obviously possible, but I'm not sure that string pooling implies suffix pooling.This is in no way D specific but say you have two constant strings. const char[] a = "1234567890"; // and const char[] b = "67890"; You could lay out the memory inside of one another. IE: if a.ptr = 1 then b.ptr = 6. I'm not sure if this has been done and I don't think it would apply very often but it would be kinda cool. I thought of this because I wanted to pre-generate hex-representations of some numbers I realized I could use half the memory if I nested them. (At least I think it would be half). Kevin.I'm pretty sure this is called string pooling.
Mar 16 2012
On Mar 16, 2012 7:45 AM, "Alex R=C3=B8nne Petersen" <xtzgzorex gmail.com> w= roteI don't see any reason why c couldn't point to element number 3 of b, andhave its length set to 3...-- - AlexAnd the previous examples were language agnostic. In D and other languages where the length of a string is stored we can nest strings anywhere inside other strings. const char[] a =3D "foofoo"; const char[] b =3D "oof"; Those can't be nested in null terminated strings, bit they can where strings have an explicit length.
Mar 16 2012
On Friday, 16 March 2012 at 12:24:45 UTC, Kevin Cox wrote:On Mar 16, 2012 7:45 AM, "Alex Rønne Petersen" <xtzgzorex gmail.com> wroteAll compile-time generated strings (like literals) in D are (guaranteed to be?) null-terminated as well.I don't see any reason why c couldn't point to element number 3 of b, andhave its length set to 3...-- - AlexAnd the previous examples were language agnostic. In D and other languages where the length of a string is stored we can nest strings anywhere inside other strings. const char[] a = "foofoo"; const char[] b = "oof"; Those can't be nested in null terminated strings, bit they can where strings have an explicit length.
Mar 16 2012
On 16/03/12 13:24, Kevin Cox wrote:On Mar 16, 2012 7:45 AM, "Alex Rønne Petersen" <xtzgzorex gmail.com <mailto:xtzgzorex gmail.com>> wrote > > I don't see any reason why c couldn't point to element number 3 of b, and have its length set to 3... > > -- > - Alex And the previous examples were language agnostic. In D and other languages where the length of a string is stored we can nest strings anywhere inside other strings. const char[] a = "foofoo"; const char[] b = "oof"; Those can't be nested in null terminated strings, bit they can where strings have an explicit length.Unfortunately string literals in D have an implicit \0 added beyond the end, so we don't have much more freedom than C.
Mar 16 2012
On Fri, Mar 16, 2012 at 08:24:34AM -0400, Kevin Cox wrote: [...]And the previous examples were language agnostic. In D and other languages where the length of a string is stored we can nest strings anywhere inside other strings. const char[] a = "foofoo"; const char[] b = "oof"; Those can't be nested in null terminated strings, bit they can where strings have an explicit length.More to the point, does dmd perform this optimization currently? T -- Mediocrity has been pushed to extremes.
Mar 16 2012
On 03/16/2012 03:28 PM, H. S. Teoh wrote:On Fri, Mar 16, 2012 at 08:24:34AM -0400, Kevin Cox wrote: [...]No. immutable string a = "123"; immutable string b = a; void main(){writeln(a.ptr is b.ptr);} // "false"And the previous examples were language agnostic. In D and other languages where the length of a string is stored we can nest strings anywhere inside other strings. const char[] a = "foofoo"; const char[] b = "oof"; Those can't be nested in null terminated strings, bit they can where strings have an explicit length.More to the point, does dmd perform this optimization currently? T
Mar 16 2012
On Friday, 16 March 2012 at 15:41:32 UTC, Timon Gehr wrote:On 03/16/2012 03:28 PM, H. S. Teoh wrote:It actually does, but only identical strings. It doesn't seem to do strings within strings. void foo(string a){ string b = "123"; writeln(a is b); } void main(){ string a = "123"; string b = "456"; string c = "123456"; foo(a); foo(b); foo(c); } Prints: true false falseMore to the point, does dmd perform this optimization currently? TNo. immutable string a = "123"; immutable string b = a; void main(){writeln(a.ptr is b.ptr);} // "false"
Mar 16 2012
On Friday, 16 March 2012 at 18:44:53 UTC, Xinok wrote:On Friday, 16 March 2012 at 15:41:32 UTC, Timon Gehr wrote:Captain obvious to the rescue, 'is' is false if the strings are of different lengths >.<. But it still stands, D doesn't dedup strings within strings. void main(){ string a = "123"; string b = "123456"; writeln(a.ptr); writeln(b.ptr); writeln(a.ptr); writeln(b.ptr); } Prints: 44F080 44F090 44F080 44F090 I printed it twice to ensure it wasn't duping the strings.On 03/16/2012 03:28 PM, H. S. Teoh wrote:It actually does, but only identical strings. It doesn't seem to do strings within strings. void foo(string a){ string b = "123"; writeln(a is b); } void main(){ string a = "123"; string b = "456"; string c = "123456"; foo(a); foo(b); foo(c); } Prints: true false falseMore to the point, does dmd perform this optimization currently? TNo. immutable string a = "123"; immutable string b = a; void main(){writeln(a.ptr is b.ptr);} // "false"
Mar 16 2012
On 03/16/2012 07:52 PM, Xinok wrote:On Friday, 16 March 2012 at 18:44:53 UTC, Xinok wrote:It can't because there must be a terminating zero byte. It does not do it even if it could though. immutable string x = "123"; immutable string y = "123"; void foo(string a){ string b = "123"; writeln(a is b); } void main(){ string a = "123"; string b = "456"; string c = "456123"; foo(c[3..$]); // false writeln(x is y); // false writeln(a is x); // false writeln(b is x); // false writeln(a is y); // false writeln(b is y); // false foo(a); // true foo(b); // false }On Friday, 16 March 2012 at 15:41:32 UTC, Timon Gehr wrote:Captain obvious to the rescue, 'is' is false if the strings are of different lengths >.<. But it still stands, D doesn't dedup strings within strings. void main(){ string a = "123"; string b = "123456"; writeln(a.ptr); writeln(b.ptr); writeln(a.ptr); writeln(b.ptr); } Prints: 44F080 44F090 44F080 44F090 I printed it twice to ensure it wasn't duping the strings.On 03/16/2012 03:28 PM, H. S. Teoh wrote:It actually does, but only identical strings. It doesn't seem to do strings within strings. void foo(string a){ string b = "123"; writeln(a is b); } void main(){ string a = "123"; string b = "456"; string c = "123456"; foo(a); foo(b); foo(c); } Prints: true false falseMore to the point, does dmd perform this optimization currently? TNo. immutable string a = "123"; immutable string b = a; void main(){writeln(a.ptr is b.ptr);} // "false"
Mar 16 2012
On Friday, 16 March 2012 at 18:56:00 UTC, Timon Gehr wrote:It can't because there must be a terminating zero byte. It does not do it even if it could though. immutable string x = "123"; immutable string y = "123"; void foo(string a){ string b = "123"; writeln(a is b); } void main(){ string a = "123"; string b = "456"; string c = "456123"; foo(c[3..$]); // false writeln(x is y); // false writeln(a is x); // false writeln(b is x); // false writeln(a is y); // false writeln(b is y); // false foo(a); // true foo(b); // false }So while D does pool strings, it doesn't seem to optimize globals. I couldn't find anything about it on the bug tracker.
Mar 16 2012
On Friday, 16 March 2012 at 18:44:53 UTC, Xinok wrote:It actually does, but only identical strings. It doesn't seem to do strings within strings.Don't forget that "123" is /not/ a substring of "123456" because of the invisible 0 terminator (which is there for easy compatibility with C functions).
Mar 16 2012
On Friday, 16 March 2012 at 11:41:59 UTC, Alex Rønne Petersen wrote:On 16-03-2012 12:32, Peter Alexander wrote:Neither do I, but it's more work for the compiler, and even if the compiler does string pooling, it may not look for common suffixes.On Friday, 16 March 2012 at 02:31:47 UTC, Xinok wrote:I don't see any reason why c couldn't point to element number 3 of b, and have its length set to 3...On Friday, 16 March 2012 at 02:18:27 UTC, Kevin wrote:My understanding is that string pooling just shares whole strings rather than combining suffixes. e.g. const char[] a = "fubar"; const char[] b = "fubar"; // shared const char[] c = "bar"; // not shared at all Combining suffixes is obviously possible, but I'm not sure that string pooling implies suffix pooling.This is in no way D specific but say you have two constant strings. const char[] a = "1234567890"; // and const char[] b = "67890"; You could lay out the memory inside of one another. IE: if a.ptr = 1 then b.ptr = 6. I'm not sure if this has been done and I don't think it would apply very often but it would be kinda cool. I thought of this because I wanted to pre-generate hex-representations of some numbers I realized I could use half the memory if I nested them. (At least I think it would be half). Kevin.I'm pretty sure this is called string pooling.
Mar 18 2012
On Mar 18, 2012 4:50 PM, "Peter Alexander" <peter.alexander.au gmail.com> wrote:Neither do I, but it's more work for the compiler, and even if thecompiler does string pooling, it may not look for common suffixes. It would be more work but it would have memory and cache benefits. If you stored created a set of strings ordered lexographicaly by their reverse it would not be that much overhead.
Mar 18 2012
On Thu, 15 Mar 2012 22:16:18 -0400, Kevin <kevincox.ca gmail.com> wrote:This is in no way D specific but say you have two constant strings. const char[] a = "1234567890"; // and const char[] b = "67890"; You could lay out the memory inside of one another. IE: if a.ptr = 1 then b.ptr = 6. I'm not sure if this has been done and I don't think it would apply very often but it would be kinda cool. I thought of this because I wanted to pre-generate hex-representations of some numbers I realized I could use half the memory if I nested them. (At least I think it would be half).I have done this manually in the past. In an application that ran on a 8-bit micro with 256 bytes of RAM and 4K code space, I ran out of space and was able to save quite a bit by making one large string array with all the data, and then use pointer/length combinations out of that string array. It seems like the compiler could do some work, but what about CTFE? I think this would be a cool project. But I'm not sure if CTFE can save state for later... string poolString(string s) { // look for s in existing pool, if found, return // otherwise, add to pool. } -Steve
Mar 19 2012
On Fri, 16 Mar 2012 13:16:18 +1100, Kevin <kevincox.ca gmail.com> wrote:This is in no way D specific but say you have two constant strings. const char[] a = "1234567890"; // and const char[] b = "67890"; You could lay out the memory inside of one another. IE: if a.ptr = 1 then b.ptr = 6. I'm not sure if this has been done and I don't think it would apply very often but it would be kinda cool. I thought of this because I wanted to pre-generate hex-representations of some numbers I realized I could use half the memory if I nested them. (At least I think it would be half).Is the effort to do this really an issue with today's vast amounts of RAM (virtual and real) available? How much memory are you expecting to 'save'? And is RAM address alignment an issue here also? Currently most literals are aligned on a 4 or 8-byte boundary but with this sort of pooling, some literals will not be so aligned any more. That might not be an issue but I'm just curious. -- Derek Parnell Melbourne, Australia
Mar 19 2012
On 03/19/2012 01:33 PM, Derek wrote:On Fri, 16 Mar 2012 13:16:18 +1100, Kevin <kevincox.ca gmail.com> wrote:Using less memory means having less cache misses and therefore improved performance. Saving half the memory can make quite a difference.This is in no way D specific but say you have two constant strings. const char[] a = "1234567890"; // and const char[] b = "67890"; You could lay out the memory inside of one another. IE: if a.ptr = 1 then b.ptr = 6. I'm not sure if this has been done and I don't think it would apply very often but it would be kinda cool. I thought of this because I wanted to pre-generate hex-representations of some numbers I realized I could use half the memory if I nested them. (At least I think it would be half).Is the effort to do this really an issue with today's vast amounts of RAM (virtual and real) available? How much memory are you expecting to 'save'?
Mar 19 2012
On Tue, Mar 20, 2012 at 12:05:55AM +0100, Timon Gehr wrote:On 03/19/2012 01:33 PM, Derek wrote:While the *total* amount of memory used may not matter so much, cache locality matters a LOT. The difference between an inner loop that can run with all accessed memory within the CPU cache and an inner loop that triggers >=1 cache misses per iteration (due to accessing memory that happens to exceed cache size just by a little) is *huge*. Disregarding memory usage just because of the abundance of memory is a fallacy. T -- What do you mean the Internet isn't filled with subliminal messages? What about all those buttons marked "submit"??On Fri, 16 Mar 2012 13:16:18 +1100, Kevin <kevincox.ca gmail.com> wrote:Using less memory means having less cache misses and therefore improved performance. Saving half the memory can make quite a difference.This is in no way D specific but say you have two constant strings. const char[] a = "1234567890"; // and const char[] b = "67890"; You could lay out the memory inside of one another. IE: if a.ptr = 1 then b.ptr = 6. I'm not sure if this has been done and I don't think it would apply very often but it would be kinda cool. I thought of this because I wanted to pre-generate hex-representations of some numbers I realized I could use half the memory if I nested them. (At least I think it would be half).Is the effort to do this really an issue with today's vast amounts of RAM (virtual and real) available? How much memory are you expecting to 'save'?
Mar 19 2012
On 20 March 2012 01:33, Derek <ddparnell bigpond.com> wrote:Is the effort to do this really an issue with today's vast amounts of RAM (virtual and real) available? How much memory are you expecting to 'save'? And is RAM address alignment an issue here also? Currently most literals are aligned on a 4 or 8-byte boundary but with this sort of pooling, some literals will not be so aligned any more. That might not be an issue but I'm just curious.Gah, I hate this sentiment! It encourages lazy, poor design and practice simply because "RAM/CPU is cheap, dev time is expensive". Yes, RAM and CPU /are/ cheap, and dev time is expensive, but so is losing millions of dollars of revenue because your loading times on your app are 100ms too slow, and your conversion rate drops. This is the one thing that i hate about the Rails community, since it is their motto. Sites should be blazingly fast with today's computing power, but a ridiculous focus on "Developer productivity" has meant that no change has happened. I love it when D threads talk about whether or not the compiler does inlining, or loop unrolling, or whether it does, or should, use the correct instructions for the target. Not because I get off on talking about optimisation, but because it shows that there are still people care about squeezing every last instruction of performance, without compromising on productivity. Resources cost money, any saving of resources saves money. -- James Miller
Mar 19 2012
On Tue, Mar 20, 2012 at 12:55:29PM +1300, James Miller wrote:On 20 March 2012 01:33, Derek <ddparnell bigpond.com> wrote:Not to mention that this kind of fallacious attitude causes people to fail to realize the fact that the difference of 1 byte can make the difference between an inner loop that accesses memory entirely within the CPU cache, vs. one that causes a cache miss every iteration. The difference in performance is HUGE. (And no, I'm not suggesting we waste time optimizing bytes, but where memory can be saved, it *should* be saved. Every little bit adds up; the more compact your data structures, the more likely they will fit in the cache and the less likely you'll cause cache misses in performance-critical code.)Is the effort to do this really an issue with today's vast amounts of RAM (virtual and real) available? How much memory are you expecting to 'save'? And is RAM address alignment an issue here also? Currently most literals are aligned on a 4 or 8-byte boundary but with this sort of pooling, some literals will not be so aligned any more. That might not be an issue but I'm just curious.Gah, I hate this sentiment! It encourages lazy, poor design and practice simply because "RAM/CPU is cheap, dev time is expensive". Yes, RAM and CPU /are/ cheap, and dev time is expensive, but so is losing millions of dollars of revenue because your loading times on your app are 100ms too slow, and your conversion rate drops. This is the one thing that i hate about the Rails community, since it is their motto.Sites should be blazingly fast with today's computing power, but a ridiculous focus on "Developer productivity" has meant that no change has happened.Exactly! In spite of the fact that CPU speed has increased on the order of a millionfold since the old days, and in spite of the fact that memory capacity has increased by several orders of magnitude, today's software is STILL taking forever and two days just to load, and we STILL run out of memory and thrash to swap on almost exactly the same tasks that we did 10 years ago. Where has all the performance boost drained into? Into bloated code with over-complex designs that suck resources like a sponge due to lack of concern with resource usage, that's what.I love it when D threads talk about whether or not the compiler does inlining, or loop unrolling, or whether it does, or should, use the correct instructions for the target. Not because I get off on talking about optimisation, but because it shows that there are still people care about squeezing every last instruction of performance, without compromising on productivity.Exactly. Making the *compiler* produce better code is making a difference where it matters. The compiler will be used by hundreds of thousands of projects, so the slightest improvements carry over to all of them *at zero cost to the application programmers*. It's a win-win situation.Resources cost money, any saving of resources saves money.[...] +1. T -- English has the lovely word "defenestrate", meaning "to execute by throwing someone out a window", or more recently "to remove Windows from a computer and replace it with something useful". :-) -- John Cowan
Mar 19 2012
On 20 March 2012 13:17, H. S. Teoh <hsteoh quickfur.ath.cx> wrote:And whats more, developer productivity is not a function of the tools they use, its a function of how they use them. Sure, some tools make you more productive than others, but I swear by (g)vim for everything and it hasn't let me down. I use the command line, ssh where I need to go, all tasks that should make me "less productive" but I'm good at what i do, so there's no difference. I still spend my time in PHP dealing with platform differences between my local environment and the server environment, I still have to write checks for things that are local-only and things that are server-only. Difference is that these checks exist in production code, compiled code can cut them out. Ideally, 99% of web-apps out there would be CGI/FastCGI processes running behind light webservers like nginx. They would be compiled, native code (maybe byte-code like .NET or Java if you need something special that needs it) and run at the speed of fucking light. But they aren't. You have servers running a virtual machine, running a framework, running a web app that isn't optimized because "hey, RAM is cheap". You have scripting languages running applications that have the scope of massive enterprise software, and they aren't designed for it. I hate working with PHP, not because the language sucks (though it does) but because I know that every time someone loads a page, a ton of redundant work is done, work that could be done once, on startup, then never done again. Silverstripe has to scan the directory tree to build a manifest file to get decent performance out of what they do. But they still have to check that the files exist every time the file loads. They still have to read the file and parse it. It makes me feel ill thinking about it. Anyway, I should probably stop ranting about this. -- James MillerSites should be blazingly fast with today's computing power, but a ridiculous focus on "Developer productivity" has meant that no change has happened.Exactly! In spite of the fact that CPU speed has increased on the order of a millionfold since the old days, and in spite of the fact that memory capacity has increased by several orders of magnitude, today's software is STILL taking forever and two days just to load, and we STILL run out of memory and thrash to swap on almost exactly the same tasks that we did 10 years ago. Where has all the performance boost drained into? Into bloated code with over-complex designs that suck resources like a sponge due to lack of concern with resource usage, that's what.
Mar 19 2012