Re: Article: Increasing the D Compiler Speed by Over 75%
On 8/3/2013 1:54 PM, Andrej Mitrovic wrote: On 8/3/13, Walter Bright newshou...@digitalmars.com wrote: /delexe http://www.digitalmars.com/ctg/ctgLinkSwitches.html#delexecutable Note that this switch doesn't actually work. We've talked about this somewhere in an Optlink-related bugzilla issue. I don't recall seeing it in bugzilla. If it isn't there, please add it.
Re: Article: Increasing the D Compiler Speed by Over 75%
Another little observation: Dsymbol::toPrettyChars() potentially calls toChars() twice on each symbol (so it creates 2 copies of the string representation). Some instances of toChars() just return a literal string, but for templates it can do a bunch of work. Doesn't sounds like the most efficient approach? Saying that though, it looks like a lot of the calls to that are to build error strings that are never displayed because errors are gagged, which doesn't sound ideal either?
Re: Article: Increasing the D Compiler Speed by Over 75%
On Tuesday, 30 July 2013 at 19:05:56 UTC, Andrei Alexandrescu wrote: On 7/30/13 11:13 AM, Walter Bright wrote: On 7/30/2013 2:59 AM, Leandro Lucarella wrote: I just want to point out that being so much people getting this wrong (and even fighting to convince other people that the wrong interpretation is right) might be an indication that the message you wanted to give in that blog is not extremely clear :) It never occurred to me that anyone would have any difficulty understanding the notion of speed. After all, we deal with it every day when driving. And when applying the engine brake. Today, I reduced my speed by engine braking by 50%! Andrei You deserve a trollmaster trophy for that one :D Well done !
Re: Article: Increasing the D Compiler Speed by Over 75%
On Wednesday, 31 July 2013 at 22:58:56 UTC, Walter Bright wrote: On 7/31/2013 2:40 PM, Bill Baxter wrote: Are you serious that you can't fathom how it could be confusing to someone than talking about differences in run times? Yes. And no, I'm not talking about confusing to someone who lives in an undiscovered stone age tribe in the Amazon. I'm talking about computer programmers. Considering how many programmer think javascript is near C speed, I do believe that most of them effectively do not understand the notion of speed.
Re: Article: Increasing the D Compiler Speed by Over 75%
On Wednesday, 31 July 2013 at 22:58:32 UTC, John Colvin wrote: On Wednesday, 31 July 2013 at 21:40:45 UTC, Bill Baxter wrote: Are you serious that you can't fathom how it could be confusing to someone than talking about differences in run times? If you say something is faster than something else you want the two numbers to be something you can relate to. Like MPH. Everyone has a clear concept of what MPH is. We use it every day. So to say 25 MPH is 25% faster than 20 MPH is perfectly clear. But nobody talks about program execution speed in terms of programs per second. So I think it's pretty clear why that would be harder for people to grok than changes in car speeds or run times. It's a quite impressively unbalanced education that provides understanding of memory allocation strategies, hashing and the performance pitfalls of integer division, but not something as basic as a speed. To be fair, that is the only item of the list that involve complicated like division.
Re: Article: Increasing the D Compiler Speed by Over 75%
On Wednesday, 31 July 2013 at 23:26:32 UTC, Walter Bright wrote: On 7/31/2013 3:58 PM, John Colvin wrote: It's a quite impressively unbalanced education that provides understanding of memory allocation strategies, hashing and the performance pitfalls of integer division, but not something as basic as a speed. Have you ever seen those cards that some electrical engineers carry around, with the following equations on them: V = I * R R = V / I I = V / R ? I found it: https://docs.google.com/drawings/d/1StlhTYjiUEljnfVtFjP1BXLbixO30DIkbw-DpaYJoA0/edit?hl=enpli=1 Unbelievable. The author of it writes: I'm going to explain to you how to use this cheat sheet in case you've never seen this before. http://blog.ricardoarturocabral.com/2010/07/electronic-electrical-cheat-sheets.html Makes you want to cry. Something I discovered during my studies when helping other is that most people to not even try to understand this kind of stuff. They simply brute-force the equation to their memory and regurgitate it as needed without understanding anything. Not because their aren't capable of understanding, simply because they never figured out that equation actually are saying something (and the teaching style often do not help here). They do not relate the equation to actual phenomenon they observe. A nice example is the very basic mass times acceleration equals force. Granted that acceleration is the variation of speed, this equation means the following : - If you push something it will start to move. - If you continue pushing it will move faster and faster. - If you do not push, it won't move (or continue moving the way it was). - The heavier it is, the harder it is to move that something. Any child knows all the above, it is experienced it in everyday life. And the equation is simply the mathematical notation of this very basic experience. If you don't relate such equation to anything real, you'll have all kind of trouble remembering it, knowing when to use it or how to use it.
Re: Article: Increasing the D Compiler Speed by Over 75%
On 8/7/2013 1:46 AM, deadalnix wrote: V = I * R R = V / I I = V / R If you don't relate such equation to anything real, you'll have all kind of trouble remembering it, knowing when to use it or how to use it. Worse than that, they also do not understand the trivial algebraic manipulations to get the other two forms.
Re: Article: Increasing the D Compiler Speed by Over 75%
On 02/08/2013 14:16, Dmitry Olshansky wrote: Function CPU clocks DC accesses DC misses RTLHeap::Alloc 51638 552 3538 Obj::ledata 9936 1346 3290 Obj::fltused 7392 2948 6 cgcs_term 3892 1292 638 TemplateInstance::semantic 3724 2346 20 Obj::byte 3280 548 676 vsprintf 3056 3006 4 Random lunchtime observation: A lot of the calls to vsprintf are from TypeStruct::toDecoBuffer/TypeClass::toDecoBuffer/TypeEnum::toDecoBuffer which all do OutBuffer-printf(%s, name); Is that needed, or would changing them to OutBuffer-writestring(name); be more efficient? (it seems like it might, albeit only very slightly).
Re: Article: Increasing the D Compiler Speed by Over 75%
On 8/5/2013 6:21 AM, Richard Webb wrote: Is that needed, or would changing them to OutBuffer-writestring(name); be more efficient? Yes.
Re: Article: Increasing the D Compiler Speed by Over 75%
--snip-- Leandro Lucarella wrote: I know is technically right, I'm just saying it can be easily confused for something else that looks much better than the actual (very good) reality, and in this case is misleading. If you say something that's technically correct but hard to understand, you are not communicating your message effectively. Technically correct is the best kind of correct :D
Re: Article: Increasing the D Compiler Speed by Over 75%
On Monday, 5 August 2013 at 17:53:48 UTC, Walter Bright wrote: On 8/5/2013 6:21 AM, Richard Webb wrote: Is that needed, or would changing them to OutBuffer-writestring(name); be more efficient? Yes. https://github.com/D-Programming-Language/dmd/pull/2450
Re: Article: Increasing the D Compiler Speed by Over 75%
03-Aug-2013 03:32, Walter Bright пишет: On 8/2/2013 3:53 PM, Dmitry Olshansky wrote: Thanks, that must be it! And popping that function above another one gets Obj::far16thunk to be blamed :) Need to watch out for this sort of problem next time. Could it be due to how it works with old CV debug info format? Try compiling with -g. Actually I do, as I had no symbols w/o it. This is what I changed in win32.mak: reldmd: $(DMDMAKE) OPT=-o DEBUG=-g LFLAGS=-L/ma/co $(TARGETEXE) From this: reldmd: $(DMDMAKE) OPT=-o DEBUG= LFLAGS=-L/delexe $(TARGETEXE) I've no clue what /ma/co does here, but I guess ma is short of map and co - codeview? -- Dmitry Olshansky
Re: Article: Increasing the D Compiler Speed by Over 75%
On 8/3/2013 7:06 AM, Dmitry Olshansky wrote: 03-Aug-2013 03:32, Walter Bright пишет: On 8/2/2013 3:53 PM, Dmitry Olshansky wrote: Thanks, that must be it! And popping that function above another one gets Obj::far16thunk to be blamed :) Need to watch out for this sort of problem next time. Could it be due to how it works with old CV debug info format? Try compiling with -g. Actually I do, as I had no symbols w/o it. This is what I changed in win32.mak: reldmd: $(DMDMAKE) OPT=-o DEBUG=-g LFLAGS=-L/ma/co $(TARGETEXE) From this: reldmd: $(DMDMAKE) OPT=-o DEBUG= LFLAGS=-L/delexe $(TARGETEXE) I've no clue what /ma/co does here, but I guess ma is short of map and co - codeview? /map http://www.digitalmars.com/ctg/ctgLinkSwitches.html#map /co http://www.digitalmars.com/ctg/ctgLinkSwitches.html#codeview /delexe http://www.digitalmars.com/ctg/ctgLinkSwitches.html#delexecutable
Re: Article: Increasing the D Compiler Speed by Over 75%
On 8/3/13, Walter Bright newshou...@digitalmars.com wrote: /delexe http://www.digitalmars.com/ctg/ctgLinkSwitches.html#delexecutable Note that this switch doesn't actually work. We've talked about this somewhere in an Optlink-related bugzilla issue.
Re: Article: Increasing the D Compiler Speed by Over 75%
31-Jul-2013 22:20, Walter Bright пишет: On 7/31/2013 8:26 AM, Dmitry Olshansky wrote: Ouch... to boot it's always aligned by word size, so key % sizeof(size_t) == 0 ... rendering lower 2-3 bits useless, that would make straight slice lower bits approach rather weak :) Yeah, I realized that, too. Gotta shift it right 3 or 4 bits. And that helped a bit... Anyhow after doing a bit more pervasive integer hash power of 2 tables stand up to their promise. The pull that reaps the minor speed benefit over the original (~2% speed gain!): https://github.com/D-Programming-Language/dmd/pull/2436 Not bad given that _aaGetRValue takes only a fraction of time itself. I failed to see much of any improvement on Win32 though, allocations are dominating the picture. And sharing the joy of having a nice sampling profiler, here is what AMD CodeAnalyst have to say (top X functions by CPU clocks not halted). Original DMD: Function CPU clocks DC accesses DC misses RTLHeap::Alloc 49410 520 3624 Obj::ledata 10300 13083166 Obj::fltused 646432186 cgcs_term40181328626 TemplateInstance::semantic 3362239626 Obj::byte3212506 692 vsprintf 303030602 ScopeDsymbol::search 27801592244 _pformat 2506277216 _aaGetRvalue 2134806 304 memmove 1904108428 strlen 1804486 36 malloc 1282786 40 Parameter::foreach 1240778 34 StringTable::search 952 220 42 MD5Final 918 318 Variation of DMD with pow-2 tables: Function CPU clocks DC accesses DC misses RTLHeap::Alloc 51638 552 3538 Obj::ledata 993613463290 Obj::fltused 739229486 cgcs_term38921292638 TemplateInstance::semantic 3724234620 Obj::byte3280548 676 vsprintf 305630064 ScopeDsymbol::search 26481706220 _pformat 2560271826 memcpy 2014112246 strlen 1694494 32 _aaGetRvalue 1588658 278 Parameter::foreach 1266658 38 malloc 1198758 44 StringTable::search 970 214 24 MD5Final 866 274 2 This underlies the point that DMC RTL allocator is the biggest speed detractor. It is followed by ledata (could it be due to linear search inside?) and surprisingly the tiny Obj::fltused is draining lots of cycles (is it called that often?). -- Dmitry Olshansky
Re: Article: Increasing the D Compiler Speed by Over 75%
Walter Bright, el 30 de July a las 11:13 me escribiste: On 7/30/2013 2:59 AM, Leandro Lucarella wrote: I just want to point out that being so much people getting this wrong (and even fighting to convince other people that the wrong interpretation is right) might be an indication that the message you wanted to give in that blog is not extremely clear :) It never occurred to me that anyone would have any difficulty understanding the notion of speed. After all, we deal with it every day when driving. That's a completely different context, and I don't think anyone think in terms of percentage of speed in the daily life (you just say my car is twice as fast or stuff like that, but I think people hardly say my car is 10% faster in informal contexts). For me the problem is, because in informal contexts one tend to think in multipliers of speed, not percentages (or at least I do), is where the confusion comes from, is somehow counter intuitive. I understood what you mean, but I had to think about it, my first reaction was to think you were saying the compiler took 1/4 of the original time. Then I did the math and verified what you said was correct. But I had to do the math. I'm not say is right or wrong for people to have this reflex of thinking about multipliers, I'm just saying if you care about transmitting the message as clear as you can, is better to use numbers everybody can intuitively think about. And this is in reply to Andrei too. I understand your POV, but if your main goal is communication (instead of education about side topics), I think is better to stick with numbers and language that minimizes confusion and misinterpretations. Just a humble opinion of yours truly. -- Leandro Lucarella (AKA luca) http://llucax.com.ar/ -- GPG Key: 5F5A8D05 (F8CD F9A7 BF00 5431 4145 104C 949E BFB6 5F5A 8D05) -- You can try the best you can If you try the best you can The best you can is good enough
Re: Article: Increasing the D Compiler Speed by Over 75%
On 8/2/2013 6:16 AM, Dmitry Olshansky wrote: 31-Jul-2013 22:20, Walter Bright пишет: On 7/31/2013 8:26 AM, Dmitry Olshansky wrote: Ouch... to boot it's always aligned by word size, so key % sizeof(size_t) == 0 ... rendering lower 2-3 bits useless, that would make straight slice lower bits approach rather weak :) Yeah, I realized that, too. Gotta shift it right 3 or 4 bits. And that helped a bit... Anyhow after doing a bit more pervasive integer hash power of 2 tables stand up to their promise. The pull that reaps the minor speed benefit over the original (~2% speed gain!): https://github.com/D-Programming-Language/dmd/pull/2436 2% is worth taking. Not bad given that _aaGetRValue takes only a fraction of time itself. I failed to see much of any improvement on Win32 though, allocations are dominating the picture. And sharing the joy of having a nice sampling profiler, here is what AMD CodeAnalyst have to say (top X functions by CPU clocks not halted). Original DMD: Function CPU clocks DC accesses DC misses RTLHeap::Alloc 49410 520 3624 Obj::ledata 10300 1308 3166 Obj::fltused 6464 3218 6 cgcs_term 4018 1328 626 TemplateInstance::semantic 3362 2396 26 Obj::byte 3212 506 692 vsprintf 3030 3060 2 ScopeDsymbol::search 2780 1592 244 _pformat 2506 2772 16 _aaGetRvalue 2134 806 304 memmove 1904 1084 28 strlen 1804 486 36 malloc 1282 786 40 Parameter::foreach 1240 778 34 StringTable::search 952 220 42 MD5Final 918 318 Variation of DMD with pow-2 tables: Function CPU clocks DC accesses DC misses RTLHeap::Alloc 51638 552 3538 Obj::ledata 9936 1346 3290 Obj::fltused 7392 2948 6 cgcs_term 3892 1292 638 TemplateInstance::semantic 3724 2346 20 Obj::byte 3280 548 676 vsprintf 3056 3006 4 ScopeDsymbol::search 2648 1706 220 _pformat 2560 2718 26 memcpy 2014 1122 46 strlen 1694 494 32 _aaGetRvalue 1588 658 278 Parameter::foreach 1266 658 38 malloc 1198 758 44 StringTable::search 970 214 24 MD5Final 866 274 2 This underlies the point that DMC RTL allocator is the biggest speed detractor. It is followed by ledata (could it be due to linear search inside?) and surprisingly the tiny Obj::fltused is draining lots of cycles (is it called that often?). It's not fltused() that is taking up time, it is the static function following it. The sampling profiler you're using is unaware of non-global function names.
Re: Article: Increasing the D Compiler Speed by Over 75%
On 2013-08-02 15:44:13 +, Leandro Lucarella said: I'm not say is right or wrong for people to have this reflex of thinking about multipliers, I'm just saying if you care about transmitting the message as clear as you can, is better to use numbers everybody can intuitively think about. And this is in reply to Andrei too. I understand your POV, but if your main goal is communication (instead of education about side topics), I think is better to stick with numbers and language that minimizes confusion and misinterpretations. Just a humble opinion of yours truly. Fair enough. So what would have been a better way to convey the quantitative improvement? Thanks, Andrei
Re: Article: Increasing the D Compiler Speed by Over 75%
On Friday, 2 August 2013 at 17:16:30 UTC, Andrei Alexandrescu wrote: On 2013-08-02 15:44:13 +, Leandro Lucarella said: I'm not say is right or wrong for people to have this reflex of thinking about multipliers, I'm just saying if you care about transmitting the message as clear as you can, is better to use numbers everybody can intuitively think about. And this is in reply to Andrei too. I understand your POV, but if your main goal is communication (instead of education about side topics), I think is better to stick with numbers and language that minimizes confusion and misinterpretations. Just a humble opinion of yours truly. Fair enough. So what would have been a better way to convey the quantitative improvement? Not to speak on Leandro's behalf, but I think the obvious answer is Reduced compile times by 43%. It's much more useful to express it that way because it's easier to apply. Say I have a program that takes 100 seconds to compile. Knowing that the compilation time is reduced by 43% makes it easy to see that my program will now take 57 seconds. Knowing that compilation is 75% faster doesn't help much at all - I have to get out a calculator and divide by 1.75. It's always better to use a measure that is linear with what you care about. Here, most people care about how long their programs take to compile, not how many programs they can compile per second.
Re: Article: Increasing the D Compiler Speed by Over 75%
On 8/2/13 10:44 AM, Peter Alexander wrote: Not to speak on Leandro's behalf, but I think the obvious answer is Reduced compile times by 43%. It's much more useful to express it that way because it's easier to apply. Say I have a program that takes 100 seconds to compile. Knowing that the compilation time is reduced by 43% makes it easy to see that my program will now take 57 seconds. Knowing that compilation is 75% faster doesn't help much at all - I have to get out a calculator and divide by 1.75. It's always better to use a measure that is linear with what you care about. Here, most people care about how long their programs take to compile, not how many programs they can compile per second. That's cool, thanks! Andrei
Re: Article: Increasing the D Compiler Speed by Over 75%
Well put, you two. Exactly the same point I was trying to make, only to get accused of spouting baloney. ---bb On Fri, Aug 2, 2013 at 10:44 AM, Peter Alexander peter.alexander...@gmail.com wrote: On Friday, 2 August 2013 at 17:16:30 UTC, Andrei Alexandrescu wrote: On 2013-08-02 15:44:13 +, Leandro Lucarella said: I'm not say is right or wrong for people to have this reflex of thinking about multipliers, I'm just saying if you care about transmitting the message as clear as you can, is better to use numbers everybody can intuitively think about. And this is in reply to Andrei too. I understand your POV, but if your main goal is communication (instead of education about side topics), I think is better to stick with numbers and language that minimizes confusion and misinterpretations. Just a humble opinion of yours truly. Fair enough. So what would have been a better way to convey the quantitative improvement? Not to speak on Leandro's behalf, but I think the obvious answer is Reduced compile times by 43%. It's much more useful to express it that way because it's easier to apply. Say I have a program that takes 100 seconds to compile. Knowing that the compilation time is reduced by 43% makes it easy to see that my program will now take 57 seconds. Knowing that compilation is 75% faster doesn't help much at all - I have to get out a calculator and divide by 1.75. It's always better to use a measure that is linear with what you care about. Here, most people care about how long their programs take to compile, not how many programs they can compile per second.
Re: Article: Increasing the D Compiler Speed by Over 75%
Ha ha, I am a design/controls engineer who deals with speeds and accelerations on a daily basis and yet I was also confused by Walter's statement. I guess the confusion arises from what one expects (as opposed to understands) by the word speed in the given context. In the context of compiling my SW programs, I only see a dark console with a blocked cursor which I cannot use and every second waited will be felt directly. I don't see any action or hint of speed. This makes me think that a faster compiler supposed to make me wait less. This creates a kind of mental link between the word speed and the feeling of waiting. Hence the expectation: 50% faster compiler should make me wait less by 50%. Instead of a dark console with a blocked cursor, if I see lots of lines which are been compiled scrolling at very high speed on the screen (like when installing some programs) then I would relate speed with the number of lines scrolling. And my expectation would probably change to: 50% faster compiler would compile 50% more lines per second. What I am saying is that even though technically we understand what speed is, its the intuitive subjective feeling based on the context which causes an experience of something doesn't add up. I will stop blabbering now.
Re: Article: Increasing the D Compiler Speed by Over 75%
I am OK with the existing definition of speed, but would like to see the definition mentioned somewhere at the top. speed = lines_compiled/sec. Even though its obvious to some people, it not to me! I guess that's why all the technical docs I write have a explicit definitions section at the top in the template. I should start using it more often.
Re: Article: Increasing the D Compiler Speed by Over 75%
Andrei Alexandrescu, el 2 de August a las 10:16 me escribiste: On 2013-08-02 15:44:13 +, Leandro Lucarella said: I'm not say is right or wrong for people to have this reflex of thinking about multipliers, I'm just saying if you care about transmitting the message as clear as you can, is better to use numbers everybody can intuitively think about. And this is in reply to Andrei too. I understand your POV, but if your main goal is communication (instead of education about side topics), I think is better to stick with numbers and language that minimizes confusion and misinterpretations. Just a humble opinion of yours truly. Fair enough. So what would have been a better way to convey the quantitative improvement? Reduced execution time by half? -- Leandro Lucarella (AKA luca) http://llucax.com.ar/ -- GPG Key: 5F5A8D05 (F8CD F9A7 BF00 5431 4145 104C 949E BFB6 5F5A 8D05) -- Mi infancia fue en un loft, bien al costado del río Cazabamos correcaminos y lo azabamos en el fogón Después? Después me vine grande y la ciudad me deslumbró Jugando al tejo en Lavalle me hice amigo del bongó
Re: Article: Increasing the D Compiler Speed by Over 75%
On 8/2/2013 1:45 PM, user wrote: I am OK with the existing definition of speed, but would like to see the definition mentioned somewhere at the top. speed = lines_compiled/sec. Even though its obvious to some people, it not to me! Sigh. It's not even lines per second, it's dimensionless when using percentages. Note that I never needed to count the number of lines to get a correct percentage. I guess that's why all the technical docs I write have a explicit definitions section at the top in the template. I should start using it more often. I wouldn't even read an article that had a sidebar at the top explaining what speed was.
Re: Article: Increasing the D Compiler Speed by Over 75%
02-Aug-2013 20:47, Walter Bright пишет: On 8/2/2013 6:16 AM, Dmitry Olshansky wrote: I failed to see much of any improvement on Win32 though, allocations are dominating the picture. And sharing the joy of having a nice sampling profiler, here is what AMD CodeAnalyst have to say (top X functions by CPU clocks not halted). [snip] This underlies the point that DMC RTL allocator is the biggest speed detractor. It is followed by ledata (could it be due to linear search inside?) and surprisingly the tiny Obj::fltused is draining lots of cycles (is it called that often?). It's not fltused() that is taking up time, it is the static function following it. The sampling profiler you're using is unaware of non-global function names. Thanks, that must be it! And popping that function above another one gets Obj::far16thunk to be blamed :) Need to watch out for this sort of problem next time. Could it be due to how it works with old CV debug info format? -- Dmitry Olshansky
Re: Article: Increasing the D Compiler Speed by Over 75%
On 8/2/2013 3:53 PM, Dmitry Olshansky wrote: Thanks, that must be it! And popping that function above another one gets Obj::far16thunk to be blamed :) Need to watch out for this sort of problem next time. Could it be due to how it works with old CV debug info format? Try compiling with -g. Otherwise, you only get global symbols.
Re: Article: Increasing the D Compiler Speed by Over 75%
On Wednesday, 31 July 2013 at 22:58:56 UTC, Walter Bright wrote: On 7/31/2013 2:40 PM, Bill Baxter wrote: Are you serious that you can't fathom how it could be confusing to someone than talking about differences in run times? Yes. And no, I'm not talking about confusing to someone who lives in an undiscovered stone age tribe in the Amazon. I'm talking about computer programmers. If you say something is faster than something else you want the two numbers to be something you can relate to. Like MPH. Everyone has a clear concept of what MPH is. We use it every day. So to say 25 MPH is 25% faster than 20 MPH is perfectly clear. But nobody talks about program execution speed in terms of programs per second. Yes, they do, and certainly in lines per second. Google it and see for yourself. And as you well understand, from using the same program to compile, the number of lines cancels out when comparing speeds. There is nothing mysterious or confusing about this. Seriously. So I think it's pretty clear why that would be harder for people to grok than changes in car speeds or run times. To be blunt, Baloney! Can we please stop this dumb argument? I think the source of the confusion is that programmers only use execution times to measure execution speed and will often say that they sped up a program by 50% when they halved the execution time, implying that the speed went up by 50%. Well, as Walter points out, a real speed, ie output/sec, would go up 100% in that scenario, so the programmers' language is technically incorrect. This breaks many programmers' intuitions, hence all the complaining in this thread. However, this whole debate is a bikeshed topic, as nobody really cares if the gain was 43% or 75%, ie nobody is using that precision for any purpose anyway. Walter is technically correct, that's all that matters. On Wednesday, 31 July 2013 at 23:26:32 UTC, Walter Bright wrote: On 7/31/2013 3:58 PM, John Colvin wrote: It's a quite impressively unbalanced education that provides understanding of memory allocation strategies, hashing and the performance pitfalls of integer division, but not something as basic as a speed. Have you ever seen those cards that some electrical engineers carry around, with the following equations on them: V = I * R R = V / I I = V / R ? I found it: https://docs.google.com/drawings/d/1StlhTYjiUEljnfVtFjP1BXLbixO30DIkbw-DpaYJoA0/edit?hl=enpli=1 Unbelievable. The author of it writes: I'm going to explain to you how to use this cheat sheet in case you've never seen this before. http://blog.ricardoarturocabral.com/2010/07/electronic-electrical-cheat-sheets.html Makes you want to cry. No real electrical engineer would ever use that card, as you connote with your quotes. If they don't have Ohm's law and the resulting algebra drilled into their head, they better find another job. I suspect that chart is for amateurs from other backgrounds who happen to be doing some electrical work.
Re: Article: Increasing the D Compiler Speed by Over 75%
On Thursday, 1 August 2013 at 07:47:25 UTC, Joakim wrote: On Wednesday, 31 July 2013 at 22:58:56 UTC, Walter Bright wrote: Have you ever seen those cards that some electrical engineers carry around, with the following equations on them: V = I * R R = V / I I = V / R ? I found it: https://docs.google.com/drawings/d/1StlhTYjiUEljnfVtFjP1BXLbixO30DIkbw-DpaYJoA0/edit?hl=enpli=1 Unbelievable. The author of it writes: I'm going to explain to you how to use this cheat sheet in case you've never seen this before. http://blog.ricardoarturocabral.com/2010/07/electronic-electrical-cheat-sheets.html Makes you want to cry. No real electrical engineer would ever use that card, as you connote with your quotes. If they don't have Ohm's law and the resulting algebra drilled into their head, they better find another job. I suspect that chart is for amateurs from other backgrounds who happen to be doing some electrical work. Screw engineers, *anybody* who doesn't know these laws shouldn't be allowed anywhere *near* electricity :D
Re: Article: Increasing the D Compiler Speed by Over 75%
30-Jul-2013 22:22, Walter Bright пишет:
On 7/30/2013 11:02 AM, Dmitry Olshansky wrote:
What bothers me is that while I've been hacking at this I couldn't
shake off the
feeling that AA code assumes NO FULL HASH COLLISIONS at all?
I don't know what you mean, as it has a collision resolution system. See
embedded code below.
Yes but it does so using full _hash_ alone.
Basically Key is size_t, if we store strings in this AA and they hash to
exactly the same size_t key then you'll never find one of them.
Value _aaGetRvalue(AA* aa, Key key)
{
//printf(_aaGetRvalue(key = %p)\n, key);
if (aa)
{
size_t i;
size_t len = aa-b_length;
if (len == 4)
i = (size_t)key 3;
else if (len == 31)
i = (size_t)key % 31;
else
i = (size_t)key % len;
aaA* e = aa-b[i];
*** ^^^ obviously key is only a hash value ***
while (e)
{
if (key == e-key)
return e-value;
e = e-next;
^^^ collision resolution code ^^^ *
Here key is 32 bits. Surely 2 strings can hash to the exact same 32 bit
value. This resolves only slot collision. It doesn't resolve full hash
collision.
}
}
return NULL;// not found
}
--
Dmitry Olshansky
Re: Article: Increasing the D Compiler Speed by Over 75%
On 7/31/2013 1:49 AM, Dmitry Olshansky wrote: Here key is 32 bits. Surely 2 strings can hash to the exact same 32 bit value. No, they cannot. The hash value is a pointer to the string. The strings are already inserted into another hash table, so all strings that are the same are combined. Therefore, all unique strings hash to unique values. This resolves only slot collision. It doesn't resolve full hash collision. If it was broken the compiler wouldn't work at all :-)
Re: Article: Increasing the D Compiler Speed by Over 75%
31-Jul-2013 13:17, Walter Bright пишет: On 7/31/2013 1:49 AM, Dmitry Olshansky wrote: Here key is 32 bits. Surely 2 strings can hash to the exact same 32 bit value. No, they cannot. The hash value is a pointer to the string. The strings are already inserted into another hash table, The StringTable ? Then I have to look somewhere else entirely. so all strings that are the same are combined. Therefore, all unique strings hash to unique values. Now that sets things straight ... if they ain't hashes then it isn't a hash table in the general sense :) At least that means that contrary to my naive guess calcHash has no effect whatsoever on the distribution of keys in this AA. The real hash function could be rather biased. I've got to dig a bit deeper into the code then. This resolves only slot collision. It doesn't resolve full hash collision. If it was broken the compiler wouldn't work at all :-) I had a feeling that it can't be that bad :) -- Dmitry Olshansky
Re: Article: Increasing the D Compiler Speed by Over 75%
31-Jul-2013 19:04, Dmitry Olshansky пишет: 31-Jul-2013 13:17, Walter Bright пишет: On 7/31/2013 1:49 AM, Dmitry Olshansky wrote: [snip] so all strings that are the same are combined. Therefore, all unique strings hash to unique values. Now that sets things straight ... if they ain't hashes then it isn't a hash table in the general sense :) At least that means that contrary to my naive guess calcHash has no effect whatsoever on the distribution of keys in this AA. The real hash function could be rather biased. Ouch... to boot it's always aligned by word size, so key % sizeof(size_t) == 0 ... rendering lower 2-3 bits useless, that would make straight slice lower bits approach rather weak :) I've got to dig a bit deeper into the code then. -- Dmitry Olshansky
Re: Article: Increasing the D Compiler Speed by Over 75%
On 7/30/13 2:48 PM, Bill Baxter wrote: On Tue, Jul 30, 2013 at 12:05 PM, Andrei Alexandrescu seewebsiteforem...@erdani.org mailto:seewebsiteforem...@erdani.org wrote: On 7/30/13 11:13 AM, Walter Bright wrote: On 7/30/2013 2:59 AM, Leandro Lucarella wrote: I just want to point out that being so much people getting this wrong (and even fighting to convince other people that the wrong interpretation is right) might be an indication that the message you wanted to give in that blog is not extremely clear :) It never occurred to me that anyone would have any difficulty understanding the notion of speed. After all, we deal with it every day when driving. Yeh sure. Like I made the trip to grandmother's house in 0.25 trips/hour!. That's 25% faster than last week when I only drove at 0.2 trips/hour. I say that all the time. ;-) --bb One does say miles per hour or kilometers per hour, which is the same exact notion. Andrei
Re: Article: Increasing the D Compiler Speed by Over 75%
On Wed, Jul 31, 2013 at 10:12 AM, Andrei Alexandrescu seewebsiteforem...@erdani.org wrote: On 7/30/13 2:48 PM, Bill Baxter wrote: On Tue, Jul 30, 2013 at 12:05 PM, Andrei Alexandrescu seewebsiteforem...@erdani.org mailto:SeeWebsiteForEmail@**erdani.orgseewebsiteforem...@erdani.org wrote: On 7/30/13 11:13 AM, Walter Bright wrote: On 7/30/2013 2:59 AM, Leandro Lucarella wrote: I just want to point out that being so much people getting this wrong (and even fighting to convince other people that the wrong interpretation is right) might be an indication that the message you wanted to give in that blog is not extremely clear :) It never occurred to me that anyone would have any difficulty understanding the notion of speed. After all, we deal with it every day when driving. Yeh sure. Like I made the trip to grandmother's house in 0.25 trips/hour!. That's 25% faster than last week when I only drove at 0.2 trips/hour. I say that all the time. ;-) --bb One does say miles per hour or kilometers per hour, which is the same exact notion. That's more analogous to something like MIPS than inverse program run time. --bb
Re: Article: Increasing the D Compiler Speed by Over 75%
On 7/31/2013 8:26 AM, Dmitry Olshansky wrote: Ouch... to boot it's always aligned by word size, so key % sizeof(size_t) == 0 ... rendering lower 2-3 bits useless, that would make straight slice lower bits approach rather weak :) Yeah, I realized that, too. Gotta shift it right 3 or 4 bits.
Re: Article: Increasing the D Compiler Speed by Over 75%
On 7/31/2013 11:13 AM, Bill Baxter wrote: That's more analogous to something like MIPS than inverse program run time. If you increase the speed 100%, then the elapsed time is cut by 50%. This is a grammar school concept. It does not require an ivy league physics degree to understand. It is not obfuscated, confusing, or misleading. It doesn't rely on some rarely known formal definition of speed. I expect an audience of programmers to understand it without needing a sidebar. We talk about speed of programs all the time, including compiler speed. I previously posted google searches you can try to verify it for yourself. I.e. I'm being trolled here :-)
Re: Article: Increasing the D Compiler Speed by Over 75%
Are you serious that you can't fathom how it could be confusing to someone than talking about differences in run times? If you say something is faster than something else you want the two numbers to be something you can relate to. Like MPH. Everyone has a clear concept of what MPH is. We use it every day. So to say 25 MPH is 25% faster than 20 MPH is perfectly clear. But nobody talks about program execution speed in terms of programs per second. So I think it's pretty clear why that would be harder for people to grok than changes in car speeds or run times. Anyway, congrats on the speed improvements! When I was using D a lot, the compile times for heavily templated stuff were definitely starting to get to me. --bb On Wed, Jul 31, 2013 at 11:36 AM, Walter Bright newshou...@digitalmars.comwrote: On 7/31/2013 11:13 AM, Bill Baxter wrote: That's more analogous to something like MIPS than inverse program run time. If you increase the speed 100%, then the elapsed time is cut by 50%. This is a grammar school concept. It does not require an ivy league physics degree to understand. It is not obfuscated, confusing, or misleading. It doesn't rely on some rarely known formal definition of speed. I expect an audience of programmers to understand it without needing a sidebar. We talk about speed of programs all the time, including compiler speed. I previously posted google searches you can try to verify it for yourself. I.e. I'm being trolled here :-)
Re: Article: Increasing the D Compiler Speed by Over 75%
On 7/31/2013 2:40 PM, Bill Baxter wrote: Are you serious that you can't fathom how it could be confusing to someone than talking about differences in run times? Yes. And no, I'm not talking about confusing to someone who lives in an undiscovered stone age tribe in the Amazon. I'm talking about computer programmers. If you say something is faster than something else you want the two numbers to be something you can relate to. Like MPH. Everyone has a clear concept of what MPH is. We use it every day. So to say 25 MPH is 25% faster than 20 MPH is perfectly clear. But nobody talks about program execution speed in terms of programs per second. Yes, they do, and certainly in lines per second. Google it and see for yourself. And as you well understand, from using the same program to compile, the number of lines cancels out when comparing speeds. There is nothing mysterious or confusing about this. Seriously. So I think it's pretty clear why that would be harder for people to grok than changes in car speeds or run times. To be blunt, Baloney! Anyway, congrats on the speed improvements! When I was using D a lot, the compile times for heavily templated stuff were definitely starting to get to me. Thanks!
Re: Article: Increasing the D Compiler Speed by Over 75%
On Wednesday, 31 July 2013 at 21:40:45 UTC, Bill Baxter wrote: Are you serious that you can't fathom how it could be confusing to someone than talking about differences in run times? If you say something is faster than something else you want the two numbers to be something you can relate to. Like MPH. Everyone has a clear concept of what MPH is. We use it every day. So to say 25 MPH is 25% faster than 20 MPH is perfectly clear. But nobody talks about program execution speed in terms of programs per second. So I think it's pretty clear why that would be harder for people to grok than changes in car speeds or run times. It's a quite impressively unbalanced education that provides understanding of memory allocation strategies, hashing and the performance pitfalls of integer division, but not something as basic as a speed.
Re: Article: Increasing the D Compiler Speed by Over 75%
On 7/31/2013 3:58 PM, John Colvin wrote: It's a quite impressively unbalanced education that provides understanding of memory allocation strategies, hashing and the performance pitfalls of integer division, but not something as basic as a speed. Have you ever seen those cards that some electrical engineers carry around, with the following equations on them: V = I * R R = V / I I = V / R ? I found it: https://docs.google.com/drawings/d/1StlhTYjiUEljnfVtFjP1BXLbixO30DIkbw-DpaYJoA0/edit?hl=enpli=1 Unbelievable. The author of it writes: I'm going to explain to you how to use this cheat sheet in case you've never seen this before. http://blog.ricardoarturocabral.com/2010/07/electronic-electrical-cheat-sheets.html Makes you want to cry.
Re: Article: Increasing the D Compiler Speed by Over 75%
On Mon, 29 Jul 2013 20:05:08 +0100, John Colvin john.loughran.col...@gmail.com wrote: On Monday, 29 July 2013 at 18:34:16 UTC, Walter Bright wrote: On 7/29/2013 5:28 AM, John Colvin wrote: Seriously... Walter wouldn't have got his mechanical engineering degree if he didn't know how to calculate a speed properly. It's a grade school concept :-) A college freshman physics problem would be calculating the delta V of a rocket fired in space given the fuel weight, rocket empty weight, thrust, etc. Physics graduate / soon to be PhD student here :) It's sad how few rockets were involved in my degree... Time to fix that! https://kerbalspaceprogram.com/ R -- Using Opera's revolutionary email client: http://www.opera.com/mail/
Re: Article: Increasing the D Compiler Speed by Over 75%
On Tuesday, 30 July 2013 at 10:08:22 UTC, Leandro Lucarella wrote: JS, el 29 de July a las 22:32 me escribiste: On Monday, 29 July 2013 at 19:38:51 UTC, Walter Bright wrote: On 7/29/2013 12:08 PM, JS wrote: Trying to use distance and speed as a measure of performance of a program is just ridiculous. If you google program execution speed you'll find it's a commonly used term. Lines per second is a common measure of compiler execution speed - google compiler lines per second and see. (again, if we started with 12 second and went to 21 seconds, it would be a near 75% increase. But a 75% increase is not a 75% decrease) Speed is the reciprocal of time, meaning a decrease in time is an increase in speed. You are right, sorry. There is no difference. I think the issue is interpretation. When I read X% increase in speed I think X% faster [in time]. I just want to point out that being so much people getting this wrong (and even fighting to convince other people that the wrong interpretation is right) might be an indication that the message you wanted to give in that blog is not extremely clear :) That was my whole point. If you used some easier measure to understand (like using time instead of speed) you could have avoided all this confusion :) It depends on the audience, but to write an article that is informal then use a very formal definition of speed is just begging for problems. It's hard for me to really imagine that lines is a measurement of distance and speed is lines per second... but even if I allow this I don't understand why it is a better metric than just time alone(even though it is equivalent mathematically it is a convoluted approach). If a compiler can compile n lines per second, is that really all that useful as a direct measurement? Are you saying I have to go count the lines of code in my program? Do I count empty lines? commented lines? etc... Why don't you just give me the most direct answer? Time is really all that matters, everything else is just obfuscation.
Re: Article: Increasing the D Compiler Speed by Over 75%
On 7/30/13 4:10 AM, JS wrote: It depends on the audience, but to write an article that is informal then use a very formal definition of speed is just begging for problems. It's hard for me to really imagine that lines is a measurement of distance and speed is lines per second... but even if I allow this I don't understand why it is a better metric than just time alone(even though it is equivalent mathematically it is a convoluted approach). If a compiler can compile n lines per second, is that really all that useful as a direct measurement? Are you saying I have to go count the lines of code in my program? Do I count empty lines? commented lines? etc... Why don't you just give me the most direct answer? Time is really all that matters, everything else is just obfuscation. This is wrong on many levels. Andrei
Re: Article: Increasing the D Compiler Speed by Over 75%
On 7/30/13 2:59 AM, Leandro Lucarella wrote: I just want to point out that being so much people getting this wrong (and even fighting to convince other people that the wrong interpretation is right) might be an indication that the message you wanted to give in that blog is not extremely clear :) That was my whole point. If you used some easier measure to understand (like using time instead of speed) you could have avoided all this confusion :) I tend to disagree on this, and I think the title of the article is good as is (I've reviewed it). I'd say if a programmer doesn't have a clear notion of what speed is and how comparisons go etc., they better learn it pronto. There's nothing complicated here, and if something is not obvious to some readers this is even better because the article serves as an educational tool in more ways than one. Speed involves time at the denominator, i.e. seconds come to the power of -1. I don't think it's fair to negotiate whether this is expected. Every engineer must know this. Percentage changes go as follows. If you increase something by 100% it means you doubled it. If you decrease something by 50% it means you halved it. Everything else can be easily derived from these. Again, I consider this non-negotiable background knowledge. Andrei
Re: Article: Increasing the D Compiler Speed by Over 75%
On 7/30/2013 11:02 AM, Dmitry Olshansky wrote:
26-Jul-2013 23:17, Walter Bright пишет:
How about a pull request so we can try it out?
Preliminary pull is here:
https://github.com/D-Programming-Language/dmd/pull/2436
So far it looses a bit.
:-) That's often been my experience.
I'm still playing with it, looking at load factor,
distribution of sizes, profiling.
So far observations are that SpookyHash is slower then the one that was there
thus stealing a few percents of speed. That is then hardly regained by a faster
lookup of a slot:
almost all of large tables were 31 in size and you have special case for that
anyway.
What bothers me is that while I've been hacking at this I couldn't shake off the
feeling that AA code assumes NO FULL HASH COLLISIONS at all?
I don't know what you mean, as it has a collision resolution system. See
embedded code below.
Isn't that betting on luck (and a crude hash) a little too much (esp in 32 bit
mode)?
That is e.g. in code pasted from aav.c Key is only a hash and there is no way
whatsoever to discern a full hash collision.
Value _aaGetRvalue(AA* aa, Key key)
{
//printf(_aaGetRvalue(key = %p)\n, key);
if (aa)
{
size_t i;
size_t len = aa-b_length;
if (len == 4)
i = (size_t)key 3;
else if (len == 31)
i = (size_t)key % 31;
else
i = (size_t)key % len;
aaA* e = aa-b[i];
while (e)
{
if (key == e-key)
return e-value;
e = e-next;
^^^ collision resolution code ^^^ *
}
}
return NULL;// not found
}
Re: Article: Increasing the D Compiler Speed by Over 75%
On 7/30/13 11:13 AM, Walter Bright wrote: On 7/30/2013 2:59 AM, Leandro Lucarella wrote: I just want to point out that being so much people getting this wrong (and even fighting to convince other people that the wrong interpretation is right) might be an indication that the message you wanted to give in that blog is not extremely clear :) It never occurred to me that anyone would have any difficulty understanding the notion of speed. After all, we deal with it every day when driving. And when applying the engine brake. Today, I reduced my speed by engine braking by 50%! Andrei
Re: Article: Increasing the D Compiler Speed by Over 75%
On Tue, Jul 30, 2013 at 12:05 PM, Andrei Alexandrescu seewebsiteforem...@erdani.org wrote: On 7/30/13 11:13 AM, Walter Bright wrote: On 7/30/2013 2:59 AM, Leandro Lucarella wrote: I just want to point out that being so much people getting this wrong (and even fighting to convince other people that the wrong interpretation is right) might be an indication that the message you wanted to give in that blog is not extremely clear :) It never occurred to me that anyone would have any difficulty understanding the notion of speed. After all, we deal with it every day when driving. Yeh sure. Like I made the trip to grandmother's house in 0.25 trips/hour!. That's 25% faster than last week when I only drove at 0.2 trips/hour. I say that all the time. ;-) --bb
Re: Article: Increasing the D Compiler Speed by Over 75%
On Thursday, 25 July 2013 at 21:27:47 UTC, Walter Bright wrote: On 7/25/2013 11:49 AM, Dmitry S wrote: I am also confused by the numbers. What I see at the end of the article is 21.56 seconds, and the latest development version does it in 12.19, which is really a 43% improvement. (Which is really great too.) 21.56/12.19 is 1.77, i.e. a 75% improvement in speed. A reduction in time would be the reciprocal of that. Actually, it is a 43% speed improvement. 0.43*21.56 = 9.27s So if it is 43% faster, it means it's reduced the time by 9.27s or, 21.56 - 9.27 = 12.28 seconds total. Now, if we started at 12.28 seconds and it jumped to 21.56 then it would be 21.56/12.19 = 1.77 == 77% longer. 21.56/12.19 != 12.19/21.56. The order matters. To make it obvious. Suppose the running time is 20 seconds. You optimize it, it is 100% **faster**(= 1.0*20 = 20s seconds), then it takes 0 seconds(20 - 20). Suppose the running time is 20 seconds, you screw it up, it takes 40 seconds, now it is 100% slower(1.0*20 = 20, and 20 + 20 = 40). In both cases there is a difference of 20 seconds BUT they mean very different things. A 20% increase is not calculated the same as a 20% decrease. That is, (A - B)/A != (A - B)/B. The LHS is relative to A and the RHS is relative to B. So (21.56 - 12.19)/21.56 = 9.37/21.56 = 43% or 1 - 12.19/21.56 = 1 - 0.57 = 0.43 To make the numbers simple, 20 second original, 10 second new. How much faster is the new version? it is 10 seconds faster, or in percent, 1 - 10/20 = 0.5% (BUT if we started with 10 seconds then it would be increase of 100%) The numbers are very close to the original, but not very close to 75%. Basically you are calculating the percentage as if you slowed down the program... but it is not the same. Another example will suffice: Suppose you have 1000$. You lose 10% of it, or 100$. You now have 900$. You gain 10% of it, or 90$. You now have 990$! (Where did the 10$ go?) This is why the stock market and economy is much worse than 2007 even though the numbers look the same. Easier: Suppose you have 1000$ loose 99% then gain 99%, you have only (1000*0.01)*1.99 = 10*1.99 = 19.9... no where near your original amount. (Even though the DIJA isn't a percentage this issue does creep into the calculation due to inflation and other factors)
Re: Article: Increasing the D Compiler Speed by Over 75%
On Monday, 29 July 2013 at 11:46:05 UTC, Leandro Motta Barros
wrote:
This may be off topic, but here I go anyway...
Back in the school days, I joked that the Halting Problem is
actually
easy to solve with a Turing Machine. Since a Turing Machine is a
theoretical device that exists only in our imagination, we can
just
suppose that it is infinitely fast. So, we simply have to load
our
program in the machine and run it. If the machine doesn't stop
immediately, it means that it will run forever.
And what does this have to do with DMD?
Well, I kinda have the same feeling when using it. For my
~10kloc
project, I still haven't felt a real need to use a real build
system.
I just dmd *.d. If any measurable time passes without any error
message appearing in the console, I know that my compiled
successfully
(and it is the linker that is running now).
BTW, 10kloc is not such a large codebase, but this is with DMD
2.063
anyhow, before those improvents ;-)
LMB
The halting problem isn't about something taking an infinite
amount of time but about the decidability of it.
For example, we can write a program that will take forever but if
it is known to do so and will never halt, then there is nothing
special about it.
For example, for(;;); in an infinite loop and will never
halt(except when you turn the power off ;) but it's halting state
is completely known.
Halting problems are much more complex.
Even something like
for(;;)
{
if (random() == 3) break;
}
is decidable(it will halt after some time).
I would write a program that is undecidable but the margin is too
short! ;)
Re: Article: Increasing the D Compiler Speed by Over 75%
On Monday, 29 July 2013 at 10:15:31 UTC, JS wrote: On Thursday, 25 July 2013 at 21:27:47 UTC, Walter Bright wrote: On 7/25/2013 11:49 AM, Dmitry S wrote: I am also confused by the numbers. What I see at the end of the article is 21.56 seconds, and the latest development version does it in 12.19, which is really a 43% improvement. (Which is really great too.) 21.56/12.19 is 1.77, i.e. a 75% improvement in speed. A reduction in time would be the reciprocal of that. Actually, it is a 43% speed improvement. 0.43*21.56 = 9.27s So if it is 43% faster, it means it's reduced the time by 9.27s or, 21.56 - 9.27 = 12.28 seconds total. Now, if we started at 12.28 seconds and it jumped to 21.56 then it would be 21.56/12.19 = 1.77 == 77% longer. 21.56/12.19 != 12.19/21.56. The order matters. To make it obvious. Suppose the running time is 20 seconds. You optimize it, it is 100% **faster**(= 1.0*20 = 20s seconds), then it takes 0 seconds(20 - 20). That is how you fail a physics class. s = d/t= t = d/s 100% increase in s = 2*s let s_new = 2*s t_new = d / s_new let d = 1 program (s is measured in programs / unit time_ therefore: t_new = 1 / s_new = 1 / (2 * s) = 0.5 * 1/s = 0.5 * t Seriously... Walter wouldn't have got his mechanical engineering degree if he didn't know how to calculate a speed properly.
Re: Article: Increasing the D Compiler Speed by Over 75%
On Monday, 29 July 2013 at 12:35:59 UTC, John Colvin wrote:
On Monday, 29 July 2013 at 12:17:22 UTC, JS wrote:
Even something like
for(;;)
{
if (random() == 3) break;
}
is decidable(it will halt after some time).
That program has a finite average runtime, but its maximum
runtime is unbounded. You can't actually say it *will* halt.
For any given input (in this case 0 inputs) one cannot tell
whether the program will eventually halt, therefore it is
undecidable.
I have formal background in CS so I might have got that totally
wrong.
sorry, that should be I have NO formal background in CS
Re: Article: Increasing the D Compiler Speed by Over 75%
On Monday, 29 July 2013 at 12:36:36 UTC, John Colvin wrote:
On Monday, 29 July 2013 at 12:35:59 UTC, John Colvin wrote:
On Monday, 29 July 2013 at 12:17:22 UTC, JS wrote:
Even something like
for(;;)
{
if (random() == 3) break;
}
is decidable(it will halt after some time).
That program has a finite average runtime, but its maximum
runtime is unbounded. You can't actually say it *will* halt.
For any given input (in this case 0 inputs) one cannot tell
whether the program will eventually halt, therefore it is
undecidable.
I have formal background in CS so I might have got that
totally wrong.
sorry, that should be I have NO formal background in CS
No, again, it isn't about infinite run time.
decidability != infinite run time.
to simplify, let's look at the program,
for(;;) if (random() == 0) break;
where random() returns a random number, not necessarily uniform,
between 0 and 1.
Same problem just easier to see.
Since there must be a chance for 0 to occur, the program must
halt, regardless of how long it takes, even if it takes an
infinite amount of time.
That is, the run time of the program may approach infinity BUT it
will halt at some point because by the definition of random, 0
must occur... else it's not random.
So, by the fact that random, must cover the entire range, even if
it takes it an infinitely long time(so to speak), we know that
the program must halt. We don't care how long it will take but
just that we can decide that it will.
The only way you could be right is if random wasn't random and 0
was never returned... in that case the program would not halt...
BUT then we could decide that it never would halt...
In both cases, we can decide the outcome... if random is known to
produce 0 then it will halt, if it can't... then it won't.
But random must produce a 0 or not a 0 in an infinite amount of
time. (either 0 is in the range of random or not).
That is, the halting state of the program is not random even
though it looks like it. (again, it's not how long it takes but
if we can decide the outcome... which, in this case, rests on the
decidability of random)
Another way to see this, flipping a fair coin has 0 probability
of producing an infinite series of tails.
Why?
After N flips, the probability of flipping exactly N tails is 1/N
- 0.
Re: Article: Increasing the D Compiler Speed by Over 75%
On Monday, 29 July 2013 at 13:05:10 UTC, JS wrote:
On Monday, 29 July 2013 at 12:36:36 UTC, John Colvin wrote:
On Monday, 29 July 2013 at 12:35:59 UTC, John Colvin wrote:
On Monday, 29 July 2013 at 12:17:22 UTC, JS wrote:
Even something like
for(;;)
{
if (random() == 3) break;
}
is decidable(it will halt after some time).
That program has a finite average runtime, but its maximum
runtime is unbounded. You can't actually say it *will* halt.
For any given input (in this case 0 inputs) one cannot tell
whether the program will eventually halt, therefore it is
undecidable.
I have formal background in CS so I might have got that
totally wrong.
sorry, that should be I have NO formal background in CS
No, again, it isn't about infinite run time.
decidability != infinite run time.
to simplify, let's look at the program,
for(;;) if (random() == 0) break;
where random() returns a random number, not necessarily
uniform, between 0 and 1.
Same problem just easier to see.
Since there must be a chance for 0 to occur, the program must
halt, regardless of how long it takes, even if it takes an
infinite amount of time.
That is, the run time of the program may approach infinity BUT
it will halt at some point because by the definition of random,
0 must occur... else it's not random.
So, by the fact that random, must cover the entire range, even
if it takes it an infinitely long time(so to speak), we know
that the program must halt. We don't care how long it will take
but just that we can decide that it will.
The only way you could be right is if random wasn't random and
0 was never returned... in that case the program would not
halt... BUT then we could decide that it never would halt...
In both cases, we can decide the outcome... if random is known
to produce 0 then it will halt, if it can't... then it won't.
But random must produce a 0 or not a 0 in an infinite amount of
time. (either 0 is in the range of random or not).
That is, the halting state of the program is not random even
though it looks like it. (again, it's not how long it takes but
if we can decide the outcome... which, in this case, rests on
the decidability of random)
Another way to see this, flipping a fair coin has 0 probability
of producing an infinite series of tails.
Why?
After N flips, the probability of flipping exactly N tails is
1/N - 0.
Ok, I think I get what you mean now. The 2 states of interest for
the halting problem are, for a give input:
1) program *can* stop
2) program *will not* stop
is that correct?
Re: Article: Increasing the D Compiler Speed by Over 75%
On Monday, 29 July 2013 at 14:39:02 UTC, John Colvin wrote:
On Monday, 29 July 2013 at 13:05:10 UTC, JS wrote:
On Monday, 29 July 2013 at 12:36:36 UTC, John Colvin wrote:
On Monday, 29 July 2013 at 12:35:59 UTC, John Colvin wrote:
On Monday, 29 July 2013 at 12:17:22 UTC, JS wrote:
Even something like
for(;;)
{
if (random() == 3) break;
}
is decidable(it will halt after some time).
That program has a finite average runtime, but its maximum
runtime is unbounded. You can't actually say it *will* halt.
For any given input (in this case 0 inputs) one cannot tell
whether the program will eventually halt, therefore it is
undecidable.
I have formal background in CS so I might have got that
totally wrong.
sorry, that should be I have NO formal background in CS
No, again, it isn't about infinite run time.
decidability != infinite run time.
to simplify, let's look at the program,
for(;;) if (random() == 0) break;
where random() returns a random number, not necessarily
uniform, between 0 and 1.
Same problem just easier to see.
Since there must be a chance for 0 to occur, the program must
halt, regardless of how long it takes, even if it takes an
infinite amount of time.
That is, the run time of the program may approach infinity BUT
it will halt at some point because by the definition of
random, 0 must occur... else it's not random.
So, by the fact that random, must cover the entire range, even
if it takes it an infinitely long time(so to speak), we know
that the program must halt. We don't care how long it will
take but just that we can decide that it will.
The only way you could be right is if random wasn't random and
0 was never returned... in that case the program would not
halt... BUT then we could decide that it never would halt...
In both cases, we can decide the outcome... if random is known
to produce 0 then it will halt, if it can't... then it won't.
But random must produce a 0 or not a 0 in an infinite amount
of time. (either 0 is in the range of random or not).
That is, the halting state of the program is not random even
though it looks like it. (again, it's not how long it takes
but if we can decide the outcome... which, in this case, rests
on the decidability of random)
Another way to see this, flipping a fair coin has 0
probability of producing an infinite series of tails.
Why?
After N flips, the probability of flipping exactly N tails is
1/N - 0.
Ok, I think I get what you mean now. The 2 states of interest
for the halting problem are, for a give input:
1) program *can* stop
2) program *will not* stop
is that correct?
A program will either halt or not halt, the question is, can we
decide. Rather:
A program will either halt or not halt, or be impossible to tell.
We'd like to think we know if a program will stop or not but we
can't always know that... there are just some strange programs
that we can't figure out. The program is sort of a superposition
of halting and not halting... sort of like schrodingers cat.
For example, it is impossible to know if schrodingers cat is
alive or dead until we open the box(but suppose we never get to
open the box).
Here is another example:
main() { readln(); }
Does the program halt or not?
Yes! Just because it depends on what the user does, does not mean
the program change the fact that the program halts or not.
Basically the halting problem deals with the structural aspect of
the program itself and not the inputs on it. (this does not mean
that the input is not required)
Here is the only example that comes to mind.
main(S) { for(;;) if (S subset of S) halt; }
Ok? easy program right. Just checks if S is a subset of itself
and halts, else doesn't.
But what happens when we call it with the set of all sets?
Such a program is indeterminate. Why? Because the set of all sets
that do not contain themselves both contains itself and doesn't
contain itself. (the if statement can't be computed)
i.e., Let S = Set of all sets that do not contain themselves.
If S doesn't contain itself in, by definition, S is a subset of
itself... which is contradictory.
If S contains itself, then again, by definition, S is a set that
does not contain itself, which is contradictory.
Hence, the program give above's halting state can't be known..
or, can't be determined, or is undecidable.
All you have to do is ask yourself if it halts(for the given
input)? You can't even reason about it. Because if it does halt
then it doesn't halt.
Re: Article: Increasing the D Compiler Speed by Over 75%
On 7/29/2013 5:28 AM, John Colvin wrote: Seriously... Walter wouldn't have got his mechanical engineering degree if he didn't know how to calculate a speed properly. It's a grade school concept :-) A college freshman physics problem would be calculating the delta V of a rocket fired in space given the fuel weight, rocket empty weight, thrust, etc.
Re: Article: Increasing the D Compiler Speed by Over 75%
On 7/29/2013 4:45 AM, Leandro Motta Barros wrote: Well, I kinda have the same feeling when using it. For my ~10kloc project, I still haven't felt a real need to use a real build system. I just dmd *.d. If any measurable time passes without any error message appearing in the console, I know that my compiled successfully (and it is the linker that is running now). That goes back to the interesting effect that every order of magnitude improvement in compile speed has a transformative effect on development procedure. (For example, if it took overnight to compile, Brad Roberts' autotester would be nigh unusable in its existing form.)
Re: Article: Increasing the D Compiler Speed by Over 75%
On Monday, 29 July 2013 at 12:28:16 UTC, John Colvin wrote: On Monday, 29 July 2013 at 10:15:31 UTC, JS wrote: On Thursday, 25 July 2013 at 21:27:47 UTC, Walter Bright wrote: On 7/25/2013 11:49 AM, Dmitry S wrote: I am also confused by the numbers. What I see at the end of the article is 21.56 seconds, and the latest development version does it in 12.19, which is really a 43% improvement. (Which is really great too.) 21.56/12.19 is 1.77, i.e. a 75% improvement in speed. A reduction in time would be the reciprocal of that. Actually, it is a 43% speed improvement. 0.43*21.56 = 9.27s So if it is 43% faster, it means it's reduced the time by 9.27s or, 21.56 - 9.27 = 12.28 seconds total. Now, if we started at 12.28 seconds and it jumped to 21.56 then it would be 21.56/12.19 = 1.77 == 77% longer. 21.56/12.19 != 12.19/21.56. The order matters. To make it obvious. Suppose the running time is 20 seconds. You optimize it, it is 100% **faster**(= 1.0*20 = 20s seconds), then it takes 0 seconds(20 - 20). That is how you fail a physics class. s = d/t= t = d/s 100% increase in s = 2*s let s_new = 2*s t_new = d / s_new let d = 1 program (s is measured in programs / unit time_ therefore: t_new = 1 / s_new = 1 / (2 * s) = 0.5 * 1/s = 0.5 * t Seriously... Walter wouldn't have got his mechanical engineering degree if he didn't know how to calculate a speed properly. I'm sorry but a percentage is not related to distance, speed, or time. A percentage if a relative quantity that depends on a base for reference. Speed, time, nor distance are relative. let d = 1 program (s is measured in programs / unit time_ which is nonsense... programs / unit time? Trying to use distance and speed as a measure of performance of a program is just ridiculous. The only thing that has any meaning is the execution time and the way to compare them is taking the ratio of the old to new. Which gives a percentage change. If the change 1 then it is an increase, if 1 then it is a decrease. Btw, it should be t_new = d_new/s_new and the proper way to calculate a percentage change in time would be t_new/t_old = d_new/s_new*s_old/d_old = d_new/d_old / (s_new/s_old) If we assume the distance is constant, say it is the distance the program must travel from start to finish, then d_new = d_old and t_new/t_old = s_old/s_new or p = t_new/t_old = s_old/s_new is the percentage change of the program. Note that speed is the reciprocal of the time side, if you interpret it wrong for the program(it's not time) then you'll get the wrong answer). 21.56/12.19 = 1.77 == 77% (if you dump the 1 for some reason) 12.19/21.56 = 0.56 == 56% but only one is right... Again, it should be obvious: Starting at 21.56, let's round that to 20s. Ended at 12.19s, let's round that to 10s. 10 seconds is half of 20s, not 75%(or 25%). Note how close 50% is to 56% with how close the rounding is. It's no coincidence... It seems some people have to go back to kindergarten and study percentages! (again, if we started with 12 second and went to 21 seconds, it would be a near 75% increase. But a 75% increase is not a 75% decrease) Please study up on basic math before building any bridges. I know computers have made everyone dumb
Re: Article: Increasing the D Compiler Speed by Over 75%
On Monday, 29 July 2013 at 18:34:16 UTC, Walter Bright wrote: On 7/29/2013 5:28 AM, John Colvin wrote: Seriously... Walter wouldn't have got his mechanical engineering degree if he didn't know how to calculate a speed properly. It's a grade school concept :-) A college freshman physics problem would be calculating the delta V of a rocket fired in space given the fuel weight, rocket empty weight, thrust, etc. Physics graduate / soon to be PhD student here :) It's sad how few rockets were involved in my degree...
Re: Article: Increasing the D Compiler Speed by Over 75%
On 7/29/2013 12:08 PM, JS wrote: Trying to use distance and speed as a measure of performance of a program is just ridiculous. If you google program execution speed you'll find it's a commonly used term. Lines per second is a common measure of compiler execution speed - google compiler lines per second and see. (again, if we started with 12 second and went to 21 seconds, it would be a near 75% increase. But a 75% increase is not a 75% decrease) Speed is the reciprocal of time, meaning a decrease in time is an increase in speed.
Re: Article: Increasing the D Compiler Speed by Over 75%
On Monday, 29 July 2013 at 19:08:28 UTC, JS wrote: On Monday, 29 July 2013 at 12:28:16 UTC, John Colvin wrote: On Monday, 29 July 2013 at 10:15:31 UTC, JS wrote: On Thursday, 25 July 2013 at 21:27:47 UTC, Walter Bright wrote: On 7/25/2013 11:49 AM, Dmitry S wrote: I am also confused by the numbers. What I see at the end of the article is 21.56 seconds, and the latest development version does it in 12.19, which is really a 43% improvement. (Which is really great too.) 21.56/12.19 is 1.77, i.e. a 75% improvement in speed. A reduction in time would be the reciprocal of that. Actually, it is a 43% speed improvement. 0.43*21.56 = 9.27s So if it is 43% faster, it means it's reduced the time by 9.27s or, 21.56 - 9.27 = 12.28 seconds total. Now, if we started at 12.28 seconds and it jumped to 21.56 then it would be 21.56/12.19 = 1.77 == 77% longer. 21.56/12.19 != 12.19/21.56. The order matters. To make it obvious. Suppose the running time is 20 seconds. You optimize it, it is 100% **faster**(= 1.0*20 = 20s seconds), then it takes 0 seconds(20 - 20). That is how you fail a physics class. s = d/t= t = d/s 100% increase in s = 2*s let s_new = 2*s t_new = d / s_new let d = 1 program (s is measured in programs / unit time_ therefore: t_new = 1 / s_new = 1 / (2 * s) = 0.5 * 1/s = 0.5 * t Seriously... Walter wouldn't have got his mechanical engineering degree if he didn't know how to calculate a speed properly. I'm sorry but a percentage is not related to distance, speed, or time. A percentage if a relative quantity that depends on a base for reference. Speed, time, nor distance are relative. let d = 1 program (s is measured in programs / unit time_ which is nonsense... programs / unit time? Trying to use distance and speed as a measure of performance of a program is just ridiculous. The only thing that has any meaning is the execution time and the way to compare them is taking the ratio of the old to new. Which gives a percentage change. If the change 1 then it is an increase, if 1 then it is a decrease. Btw, it should be t_new = d_new/s_new and the proper way to calculate a percentage change in time would be t_new/t_old = d_new/s_new*s_old/d_old = d_new/d_old / (s_new/s_old) If we assume the distance is constant, say it is the distance the program must travel from start to finish, then d_new = d_old and t_new/t_old = s_old/s_new or p = t_new/t_old = s_old/s_new is the percentage change of the program. Note that speed is the reciprocal of the time side, if you interpret it wrong for the program(it's not time) then you'll get the wrong answer). 21.56/12.19 = 1.77 == 77% (if you dump the 1 for some reason) 12.19/21.56 = 0.56 == 56% but only one is right... Again, it should be obvious: Starting at 21.56, let's round that to 20s. Ended at 12.19s, let's round that to 10s. 10 seconds is half of 20s, not 75%(or 25%). Note how close 50% is to 56% with how close the rounding is. It's no coincidence... It seems some people have to go back to kindergarten and study percentages! (again, if we started with 12 second and went to 21 seconds, it would be a near 75% increase. But a 75% increase is not a 75% decrease) Please study up on basic math before building any bridges. I know computers have made everyone dumb And again: speed of original = f_old = 1 / 21.56 compilations per second speed of new = f_new = 1 / 12.19 compilations per second It's a frequency really, so I'm using f change in speed = delta_f = f_new - f_old = (1 / 12.19) - (1 / 21.56) proportional change in speed = deltaf / f_old = (f_new / f_old) - 1 = ((1 / 12.19) / (1 / 21.56)) - 1 = 0.769 percentage change in speed = 100 * 0.769 = 76.9% If something does the same work in 25% of the time, it is 1/0.25 = 4 times faster, i.e. a 300% increase in speed. After Walter's optimisations, dmd did the same work in 56.5% of the time, which is 1/0.565 = 1.769 times faster, representing a 76.9% increase in speed. The definition it's all coming from: percentage change = 100*(new - old)/old
Re: Article: Increasing the D Compiler Speed by Over 75%
On 07/29/2013 12:08 PM, JS wrote: It seems some people have to go back to kindergarten and study percentages! Do you seriously think people who follow this forum need to relearn what a percentage is? :) (again, if we started with 12 second and went to 21 seconds, it would be a near 75% increase. But a 75% increase is not a 75% decrease) Everyone knows that. I know computers have made everyone dumb Not me. Ali
Re: Article: Increasing the D Compiler Speed by Over 75%
On Monday, 29 July 2013 at 19:38:51 UTC, Walter Bright wrote: On 7/29/2013 12:08 PM, JS wrote: Trying to use distance and speed as a measure of performance of a program is just ridiculous. If you google program execution speed you'll find it's a commonly used term. Lines per second is a common measure of compiler execution speed - google compiler lines per second and see. (again, if we started with 12 second and went to 21 seconds, it would be a near 75% increase. But a 75% increase is not a 75% decrease) Speed is the reciprocal of time, meaning a decrease in time is an increase in speed. You are right, sorry. There is no difference. I think the issue is interpretation. When I read X% increase in speed I think X% faster [in time]. Since you are using speed in a technical way, then it works. I think it is deceptive, in some sense... although not necessarily intentional. The reason is very few people measure performance of a program in any other way than the time it takes to execute the program. That is all that matters in most cases... and in most cases lines per second mean nothing... but I guess in compilers it is more useful. What I'm now wondering is why you chose to use % increase in speed rather than % decrease in time? Is it because it is a larger number and looks more impressive? It think 99.% of people using D only care about the absolute time it takes to compile their code, and giving a number that they can actually use directly(instead of having to calculate first) seems more useful. By knowing you *sped* up the compiler so it is 43% faster lets me know that I should expect compilation time of my code to be approximately cut in half. When you say 75% increase in speed I have to actually do some calculation and hopefully also interpret speed properly. Nowhere in the article do you refer to the lines per second or any technical definition of speed. It's a somewhat informal article but you are using a rather formal definition of speed and it also does not directly give the user an obvious metric as just giving them the percentage change of time.
Re: Article: Increasing the D Compiler Speed by Over 75%
On Monday, 29 July 2013 at 20:19:34 UTC, John Colvin wrote: On Monday, 29 July 2013 at 19:08:28 UTC, JS wrote: Please study up on basic math before building any bridges. I know computers have made everyone dumb And again: Honestly, I don't know why you are still trying... At this point, it's not the math that's a problem anymore, it's basic communication. Back to the main subject: Congrats Walter! Those are some incredible numbers ;)
Re: Article: Increasing the D Compiler Speed by Over 75%
I've not run across anyone who says my program got faster! It went from 0.05 Hz to 0.08 Hz!. People do say my program does 10 X per second, though.
Re: Article: Increasing the D Compiler Speed by Over 75%
On Friday, 26 July 2013 at 00:08:21 UTC, Leandro Lucarella wrote: Walter Bright, el 25 de July a las 14:27 me escribiste: On 7/25/2013 11:49 AM, Dmitry S wrote: I am also confused by the numbers. What I see at the end of the article is 21.56 seconds, and the latest development version does it in 12.19, which is really a 43% improvement. (Which is really great too.) 21.56/12.19 is 1.77, i.e. a 75% improvement in speed. This is certainly misleading, is very easy to be confused with a time reduction of 75%, which one would expect to be 1/4 of the original time. :) No, a division by 4 of the total time would be a 300% improvement in speed. The article's title looks correct to me.
Re: Article: Increasing the D Compiler Speed by Over 75%
Walter Bright, el 25 de July a las 18:33 me escribiste: On 7/25/2013 4:15 PM, Leandro Lucarella wrote: Walter Bright, el 25 de July a las 14:27 me escribiste: On 7/25/2013 11:49 AM, Dmitry S wrote: I am also confused by the numbers. What I see at the end of the article is 21.56 seconds, and the latest development version does it in 12.19, which is really a 43% improvement. (Which is really great too.) 21.56/12.19 is 1.77, i.e. a 75% improvement in speed. This is certainly misleading, is very easy to be confused with a time reduction of 75%, which one would expect to be 1/4 of the original time. :) I don't think it's misleading at all. Speed is distance/time. A change in speed (which is the title) is the reciprocal of a change in time. For example, a doubling of speed (100% increase) is a halving of time (50% reduction). I know is technically right, I'm just saying it can be easily confused for something else that looks much better than the actual (very good) reality, and in this case is misleading. If you say something that's technically correct but hard to understand, you are not communicating your message effectively. -- Leandro Lucarella (AKA luca) http://llucax.com.ar/ -- GPG Key: 5F5A8D05 (F8CD F9A7 BF00 5431 4145 104C 949E BFB6 5F5A 8D05) -- No existiría el sonido del mar si faltara en la vida oreja y caracol. -- Ricardo Vaporeso. Cosquín, 1908.
Re: Article: Increasing the D Compiler Speed by Over 75%
SomeDude, el 27 de July a las 20:27 me escribiste: On Friday, 26 July 2013 at 00:08:21 UTC, Leandro Lucarella wrote: Walter Bright, el 25 de July a las 14:27 me escribiste: On 7/25/2013 11:49 AM, Dmitry S wrote: I am also confused by the numbers. What I see at the end of the article is 21.56 seconds, and the latest development version does it in 12.19, which is really a 43% improvement. (Which is really great too.) 21.56/12.19 is 1.77, i.e. a 75% improvement in speed. This is certainly misleading, is very easy to be confused with a time reduction of 75%, which one would expect to be 1/4 of the original time. :) No, a division by 4 of the total time would be a 300% improvement in speed. The article's title looks correct to me. Again, I never said is incorrect, I said is easily to read it incorrectly, which ends up sending a wrong message. -- Leandro Lucarella (AKA luca) http://llucax.com.ar/ -- GPG Key: 5F5A8D05 (F8CD F9A7 BF00 5431 4145 104C 949E BFB6 5F5A 8D05) -- Wake from your sleep, the drying of your tears, Today we escape, we escape.
Re: Article: Increasing the D Compiler Speed by Over 75%
On 26.07.2013 01:15, Leandro Lucarella wrote: Walter Bright, el 25 de July a las 14:27 me escribiste: On 7/25/2013 11:49 AM, Dmitry S wrote: I am also confused by the numbers. What I see at the end of the article is 21.56 seconds, and the latest development version does it in 12.19, which is really a 43% improvement. (Which is really great too.) 21.56/12.19 is 1.77, i.e. a 75% improvement in speed. This is certainly misleading, is very easy to be confused with a time reduction of 75%, which one would expect to be 1/4 of the original time. :) A doubling of the speed would be 100%, just saying.
Re: Article: Increasing the D Compiler Speed by Over 75%
Certainly you're technically correct about the 75% improvement in speed, but the units of speed for program execution is a little weird and unintuitive (Hz). I've not run across anyone who says my program got faster! It went from 0.05 Hz to 0.08 Hz!. I think that's why people find it a little odd to talk about speed increase rather than time decrease. On Sat, Jul 27, 2013 at 8:12 PM, torhu no@spam.invalid wrote: On 26.07.2013 01:15, Leandro Lucarella wrote: Walter Bright, el 25 de July a las 14:27 me escribiste: On 7/25/2013 11:49 AM, Dmitry S wrote: I am also confused by the numbers. What I see at the end of the article is 21.56 seconds, and the latest development version does it in 12.19, which is really a 43% improvement. (Which is really great too.) 21.56/12.19 is 1.77, i.e. a 75% improvement in speed. This is certainly misleading, is very easy to be confused with a time reduction of 75%, which one would expect to be 1/4 of the original time. :) A doubling of the speed would be 100%, just saying.
Re: Article: Increasing the D Compiler Speed by Over 75%
Walter Bright: Hash collisions are not the problem - I sized the hash bucket array to make it fairly sparse. Neither is the hash algorithm. The slowness was in the frackin' convert the hash to an index in the bucket, which is a modulus operation. Thankfully in that thread Paul Hsieh has given more precise suggestions, he's kind of expert on such matters. Bye, bearophile
Re: Article: Increasing the D Compiler Speed by Over 75%
26-Jul-2013 01:25, Walter Bright пишет: On 7/25/2013 1:00 PM, bearophile wrote: Walter Bright: It's not the hashing that's slow. It's the lookup that is. By different hashing scheme I meant different strategies in resolving hash collisions, likes double hashing, internal hashing, cuckoo hashing, and so on and on. Maybe one of such alternative strategies is more fit for the needs of dmd compilation. (I think that currently the Python dicts are using a hashing strategy different from the built-in dictionaries of D. The Python style of hashing was implemented in D some months ago, but I don't remember what happened to that project later). Hash collisions are not the problem - I sized the hash bucket array to make it fairly sparse. Neither is the hash algorithm. The slowness was in the frackin' convert the hash to an index in the bucket, which is a modulus operation. Then it's past due to finally stop the madness of modulo prime table and use a power of 2 size. In essence what modulo prime does is simply enhancing the quality of your hash function w.r.t. collisions (it helps to distribute values more evenly). Any of new decent hashes are good enough to work with plain slice the lower bits approach. Also, computing the hash is done exactly once, in the lexer. All the more reason to use good hash function and kill the modulo prime. Thereafter, all identifiers are known only by their handles, which are (not coincidentally) the pointer to the identifier, and by its very nature is unique. -- Dmitry Olshansky
Re: Article: Increasing the D Compiler Speed by Over 75%
26-Jul-2013 14:47, Dmitry Olshansky пишет: 26-Jul-2013 01:25, Walter Bright пишет: The slowness was in the frackin' convert the hash to an index in the bucket, which is a modulus operation. Then it's past due to finally stop the madness of modulo prime table and use a power of 2 size. In essence what modulo prime does is simply enhancing the quality of your hash function w.r.t. collisions (it helps to distribute values more evenly). Any of new decent hashes are good enough to work with plain slice the lower bits approach. To be more concrete: Spooky hash http://burtleburtle.net/bob/hash/spooky.html (Public domain) S-box hash http://home.comcast.net/~bretm/hash/10.html (Published paper) Or even a good ol' FNV (Public domain) http://isthe.com/chongo/tech/comp/fnv/#FNV-1a -- Dmitry Olshansky
Re: Article: Increasing the D Compiler Speed by Over 75%
On 7/26/2013 5:11 AM, Dmitry Olshansky wrote: 26-Jul-2013 14:47, Dmitry Olshansky пишет: 26-Jul-2013 01:25, Walter Bright пишет: The slowness was in the frackin' convert the hash to an index in the bucket, which is a modulus operation. Then it's past due to finally stop the madness of modulo prime table and use a power of 2 size. In essence what modulo prime does is simply enhancing the quality of your hash function w.r.t. collisions (it helps to distribute values more evenly). Any of new decent hashes are good enough to work with plain slice the lower bits approach. To be more concrete: Spooky hash http://burtleburtle.net/bob/hash/spooky.html (Public domain) S-box hash http://home.comcast.net/~bretm/hash/10.html (Published paper) Or even a good ol' FNV (Public domain) http://isthe.com/chongo/tech/comp/fnv/#FNV-1a How about a pull request so we can try it out?
Re: Article: Increasing the D Compiler Speed by Over 75%
26-Jul-2013 23:17, Walter Bright пишет: On 7/26/2013 5:11 AM, Dmitry Olshansky wrote: 26-Jul-2013 14:47, Dmitry Olshansky пишет: 26-Jul-2013 01:25, Walter Bright пишет: The slowness was in the frackin' convert the hash to an index in the bucket, which is a modulus operation. Then it's past due to finally stop the madness of modulo prime table and use a power of 2 size. In essence what modulo prime does is simply enhancing the quality of your hash function w.r.t. collisions (it helps to distribute values more evenly). Any of new decent hashes are good enough to work with plain slice the lower bits approach. To be more concrete: Spooky hash http://burtleburtle.net/bob/hash/spooky.html (Public domain) S-box hash http://home.comcast.net/~bretm/hash/10.html (Published paper) Or even a good ol' FNV (Public domain) http://isthe.com/chongo/tech/comp/fnv/#FNV-1a How about a pull request so we can try it out? Thought as much. I'll be away at the weekends but I'll surely try my hand at it afterwards. -- Dmitry Olshansky
Re: Article: Increasing the D Compiler Speed by Over 75%
Andrei Alexandrescu: http://www.reddit.com/r/programming/comments/1j1i30/increasing_the_d_compiler_speed_by_over_75/ Where is the 75% value coming from? Regarding the hashing, maybe a different hashing scheme, like Python dicts hashing could be better. Regarding Don's problems with memory used by dmd, is it a good idea to add a compilation switch like -cgc that switches on a garbage collector for the compiler (disabled on default)? Bye, bearophile
Re: Article: Increasing the D Compiler Speed by Over 75%
On 7/25/2013 11:21 AM, bearophile wrote: Andrei Alexandrescu: http://www.reddit.com/r/programming/comments/1j1i30/increasing_the_d_compiler_speed_by_over_75/ Where is the 75% value coming from? Not sure what you mean. Numbers at the end of the article. Regarding the hashing, maybe a different hashing scheme, like Python dicts hashing could be better. It's not the hashing that's slow. It's the lookup that is. Regarding Don's problems with memory used by dmd, is it a good idea to add a compilation switch like -cgc that switches on a garbage collector for the compiler (disabled on default)? It might be.
Re: Article: Increasing the D Compiler Speed by Over 75%
The biggest compile time killer in my experience is actually running out of memory and hitting the swap. My work app used to compile in about 8 seconds (on Linux btw). Then we added more and more stuff and it went up to about 20 seconds. It uses a fair amount of CTFE and template stuff, looping over almost every function in the program to generate code. Annoying... but then we added a little bit more and it skyrocketed to about 90 seconds to compile! That's unbearable. The cause was the build machine had run out of physical memory at the peak of the compile process, and started furiously swapping to disk. I fixed it by convincing them to buy more RAM, and now we're back to ~15 second compiles, but at some point the compiler will have to address this. I know donc has a dmd fork where he's doing a lot of work, completely re-engineering CTFE, so it is coming, but that will probably be the next speed increase, and we could be looking at as much as 5x in cases like mine! BTW apparently a dmd built with Microsoft's compile does the nasty in about 11 seconds rather than 30 for the std.algorithm build - comparable to the linux version with gcc. I really like dmc too, but a 3x speed increase is really significant for something that's relatively easy to do.
Re: Article: Increasing the D Compiler Speed by Over 75%
On 7/25/2013 11:30 AM, Adam D. Ruppe wrote: The biggest compile time killer in my experience is actually running out of memory and hitting the swap. My work app used to compile in about 8 seconds (on Linux btw). Then we added more and more stuff and it went up to about 20 seconds. It uses a fair amount of CTFE and template stuff, looping over almost every function in the program to generate code. Annoying... but then we added a little bit more and it skyrocketed to about 90 seconds to compile! That's unbearable. The cause was the build machine had run out of physical memory at the peak of the compile process, and started furiously swapping to disk. I fixed it by convincing them to buy more RAM, and now we're back to ~15 second compiles, but at some point the compiler will have to address this. I know donc has a dmd fork where he's doing a lot of work, completely re-engineering CTFE, so it is coming, but that will probably be the next speed increase, and we could be looking at as much as 5x in cases like mine! I know the memory consumption is a problem, but it's much harder to fix. BTW apparently a dmd built with Microsoft's compile does the nasty in about 11 seconds rather than 30 for the std.algorithm build - comparable to the linux version with gcc. I really like dmc too, but a 3x speed increase is really significant for something that's relatively easy to do. An interesting project would be to research the specific cause of the difference.
Re: Article: Increasing the D Compiler Speed by Over 75%
On Thursday, 25 July 2013 at 19:07:02 UTC, Walter Bright wrote: On 7/25/2013 11:30 AM, Adam D. Ruppe wrote: The biggest compile time killer in my experience is actually running out of memory and hitting the swap. My work app used to compile in about 8 seconds (on Linux btw). Then we added more and more stuff and it went up to about 20 seconds. It uses a fair amount of CTFE and template stuff, looping over almost every function in the program to generate code. Annoying... but then we added a little bit more and it skyrocketed to about 90 seconds to compile! That's unbearable. The cause was the build machine had run out of physical memory at the peak of the compile process, and started furiously swapping to disk. I fixed it by convincing them to buy more RAM, and now we're back to ~15 second compiles, but at some point the compiler will have to address this. I know donc has a dmd fork where he's doing a lot of work, completely re-engineering CTFE, so it is coming, but that will probably be the next speed increase, and we could be looking at as much as 5x in cases like mine! I know the memory consumption is a problem, but it's much harder to fix. Obstacks are a popular approach in compilers. Allocation is the simple pointer-bump, so it should maintain the new speed. Deallocation can be done blockwise. Works great, if you know the lifetime of the objects.
Re: Article: Increasing the D Compiler Speed by Over 75%
On 7/25/2013 12:26 PM, qznc wrote: if you know the lifetime of the objects. Aye, there's the rub! And woe to you if you get that wrong.
Re: Article: Increasing the D Compiler Speed by Over 75%
Walter Bright: It's not the hashing that's slow. It's the lookup that is. By different hashing scheme I meant different strategies in resolving hash collisions, likes double hashing, internal hashing, cuckoo hashing, and so on and on. Maybe one of such alternative strategies is more fit for the needs of dmd compilation. (I think that currently the Python dicts are using a hashing strategy different from the built-in dictionaries of D. The Python style of hashing was implemented in D some months ago, but I don't remember what happened to that project later). Bye, bearophile
Re: Article: Increasing the D Compiler Speed by Over 75%
On Thu, Jul 25, 2013 at 2:25 PM, Walter Bright newshou...@digitalmars.comwrote: On 7/25/2013 11:21 AM, bearophile wrote: Andrei Alexandrescu: http://www.reddit.com/r/**programming/comments/1j1i30/** increasing_the_d_compiler_**speed_by_over_75/http://www.reddit.com/r/programming/comments/1j1i30/increasing_the_d_compiler_speed_by_over_75/ Where is the 75% value coming from? Not sure what you mean. Numbers at the end of the article. I am also confused by the numbers. What I see at the end of the article is 21.56 seconds, and the latest development version does it in 12.19, which is really a 43% improvement. (Which is really great too.) Regarding the hashing, maybe a different hashing scheme, like Python dicts hashing could be better. It's not the hashing that's slow. It's the lookup that is. Regarding Don's problems with memory used by dmd, is it a good idea to add a compilation switch like -cgc that switches on a garbage collector for the compiler (disabled on default)? It might be.
Re: Article: Increasing the D Compiler Speed by Over 75%
On 7/25/2013 11:49 AM, Dmitry S wrote: I am also confused by the numbers. What I see at the end of the article is 21.56 seconds, and the latest development version does it in 12.19, which is really a 43% improvement. (Which is really great too.) 21.56/12.19 is 1.77, i.e. a 75% improvement in speed. A reduction in time would be the reciprocal of that.
Re: Article: Increasing the D Compiler Speed by Over 75%
On Thursday, July 25, 2013 14:25:20 Walter Bright wrote: Also, computing the hash is done exactly once, in the lexer. Thereafter, all identifiers are known only by their handles, which are (not coincidentally) the pointer to the identifier, and by its very nature is unique. I've always thought that that was a neat trick. But you seem to have quite a few of those in the compiler that you've come up with or learned about over the years. We're definitely benefiting from your experience. - Jonathan M Davis
Re: Article: Increasing the D Compiler Speed by Over 75%
On 7/25/2013 3:54 PM, Vladimir Panteleev wrote: Like string interning? Exactly.
Re: Article: Increasing the D Compiler Speed by Over 75%
On 7/25/2013 4:15 PM, Leandro Lucarella wrote: Walter Bright, el 25 de July a las 14:27 me escribiste: On 7/25/2013 11:49 AM, Dmitry S wrote: I am also confused by the numbers. What I see at the end of the article is 21.56 seconds, and the latest development version does it in 12.19, which is really a 43% improvement. (Which is really great too.) 21.56/12.19 is 1.77, i.e. a 75% improvement in speed. This is certainly misleading, is very easy to be confused with a time reduction of 75%, which one would expect to be 1/4 of the original time. :) I don't think it's misleading at all. Speed is distance/time. A change in speed (which is the title) is the reciprocal of a change in time. For example, a doubling of speed (100% increase) is a halving of time (50% reduction).
Re: Article: Increasing the D Compiler Speed by Over 75%
In IT speed is time. Weight, volume and size are bytes. Kilo- is 1024. And other non-SI weird stuff.
Re: Article: Increasing the D Compiler Speed by Over 75%
In IT speed is time. That's probably because IT folks are loose with units. Though pedantism is ok.
