14 ms·
D compilation is too slow and I am forking the compiler
- spatz 8y agoWhy are the results in a video instead of a table? I don't want to wait for dmd to know how much faster you made it.
- CyberShadow 8y ago> Why are the results in a video instead of a table? Seeing is believing! :) > I don't want to wait for dmd to know how much faster you made it. Here are the timings from the video in table form: Normal compilation (without forking): 9.163 seconds Full compilation + creating forks: 10.464 seconds Final step only (code generation + linking): 2.847 seconds After editing entry point file only: 3.792 seconds After editing deep dependency (first build): 9.562 seconds After editing deep dependency (second build): 4.675 seconds
- sam0x17 8y agowould have preferred this format as well. I hate when the goods are buried in a video.
- CJefferson 8y agoI wish that Jupyter used some kind of similar trick, to allow quickly recalculating a workbook starting at some cell.
- deleted 8y ago[deleted]
- Waterluvian 8y agoIf a notebook was written functionally without side effects, couldn't each function be explicitly or implicitly decorated with an @memoized ?
- dooglius 8y agoThat's not really how notebooks are written, at least in my experience. Even if there aren't side effects, work is often done at the lowest level without defining functions at all. Also, the fact that function definitions can change makes it tricky, and I suspect you'd run into lots of subtle issues: e.g. if you modified a function foo and a subsequent function bar calls foo, then I think calls to bar would return stale memoized data.
- Waterluvian 8y agoYes, agreed. I'm spitballing. I was thinking about how a hypothetical type of notebook could be structured in frames, where each frame can have side effects, but ultimately its input comes from the output of the previous frame. So each frame could be memoized. The UI could indicate what frames are being re-processed. I'm basically thinking about ArcGIS Model Builder[1] that I used a lot in university. It was a great way to make complex process pipelines for GIS data, but only re-run the pieces that change. It allowed me to experiment at a very fast pace. [1] http://pro.arcgis.com/en/pro-app/help/analysis/geoprocessing/modelbuilder/what-is-modelbuilder-.htm http://pro.arcgis.com/en/pro-app/help/analysis/geoprocessing...
- thomasballinger 8y agoThe Jupyter models is hard for this, but if you only allow in-order execution (like a repl, say IPython whose kernel is used in Jupyter) you could do something like this. We tried plugging in the rlundo tool https://github.com/thomasballinger/rlundo https://github.com/thomasballinger/rlundo to IPython, it works ok, see http://ballingt.com/interactive-interpreter-undo/ http://ballingt.com/interactive-interpreter-undo/ for the long story. I wanted something like this for live programming and felt like I needed to write my own interpreter because the behavior you need is so different: http://dalsegno.ballingt.com http://dalsegno.ballingt.com
- auscompgeek 8y agoWhat's the story over in gdc and ldc land? I presume since the plumbing for this sort of thing is already there (presumably), they might already be doing these sorts of AOT/incremental builds.
- CyberShadow 8y agoThey share the same frontend as DMD, which doesn't have any built-in capacity to hibernate/serialize compilation results (parsed AST) to disk. I haven't tried applying this to either compiler. Being able to perform code generation serially would benefit those the most, because their backends are considerably slower than DMD's, however the template instantiation problem currently prevents that. I don't think it's insurmountable, probably just needs someone very familiar with that part of the compiler to look at it.
- WalterBright 8y ago> doesn't have any built-in capacity to hibernate/serialize compilation results (parsed AST) to disk It turns out there isn't much purpose to that. DMD can build an AST from source so fast, that building an AST from parsing a serialized version will hardly be any faster. Vladimir sidestepped that by saving a memory image via fork.
- bhengaij 8y agoI thought D was proud of compilation times and claimed to be useful as a scripting language?
- giancarlostoro 8y agoIt's pretty damn fast every time I use it, but I don't do as much metaprogramming, which doesn't surprise me that a specific portion of D takes up time, it makes total sense to me that metaprogramming would take up a bit of time, and throw in some regex and voila, but he's definitely a D wizard in my book, I've known his work for a while now. I'm laughing at the fact 7 seconds is too long, I think it's a reasonable amount of time, but I'm usually compiling C#. The most time for me when building D is when pulling in libraries using dub (which potentially could be improved, but I'm no expert in the matter) although if I enable parallel compilation that usually breezes on by through my code.
- CyberShadow 8y agoCorrect. The language is designed to allow code written in it to compile quickly, and the reference implementation is very fast (both the front-end, and back-end). Small, script-size programs compile quickly. However, D's compile-time metaprogramming facilities allowed us to get ambitious in some places... for instance, std.uni precomputes some Unicode lookup tables during compilation, and std.regex makes heavy use of metaprogramming to compile regular expression strings to D code, again during compilation. As a result, making use of those features will result in heavier load on the compiler.
- Asooka 8y agoI don't like code that generates stuff at compile time precisely for this reason - I would much rather use some template language to pre-generate the source (I've even seen php used) and then compile it quickly. Of course that then needs support from the build system to correctly invoke the generator when the templates change and you run the risk of some developer changing the generated source instead of the template and wreaking havoc. I would very much like to have my cake and eat it - powerful code generation facilities in the language itself, but with a compiler that's as smart as the build system and can cache these for reuse when recompiling the same file. That would also allow easy integration with IDEs. For now, I've decided that the better balance is generating code using an external generator, checking everything in source control and requiring responsible people to do code review. YMMV of course, depending on what you're compiling and who you're working with.
- simonsaidit 8y ago7 seconds slow.. I was happy when I decreased the 32 hours build to 4 hours.
- jstimpfle 8y ago7 seconds for a rebuild after a small edit is already a little unergonomic when you are iterating heavily. But it all depends on the project. Simple C-style code should compile at ~1M lines of code per second on today's machines without heavy optimization, and maybe compiling on 4 cores or so. (Not possible with common infrastructure like C, gcc/clang/msvc, large headers per compilation unit, many small files, object file style linking! and the awfully slow linkers (I wonder if they could be faster))
- pif 8y ago> ... should compile at ~1M lines of code per second ... > Not possible with common infrastructure If it is not possible with common infrastructure, what do base your estimate on?
- jstimpfle 8y agoMy own experiments. I have recently bought a new PC with an i5-7600 and my own pascal parser, written in straightforward unoptimized C, parses about 2M lines of code per second on a single thread. Also I'm following Jonathan Blow's streams (Jai language). With his own trivial x64 backend he has/had a very real compilation speed of 80K lines/s, and only the parser was parallelized. I think he indends to improve that to 800K lines/s. Note that his language is quite a bit more work to compile than a basic C-like language (which is about as easy as you can get if you discount the parsing model).
- Sir_Cmpwn 8y agoI'm not sure what you're talking about with respect to the C compiler. C compilers are the fastest around even before being paralllelized - and they can be.
- lyrachord 8y agoD compilation: Not only slow but also high usage of memory. f.e. a simple program with searching and regex eats 2-3 G memory. sigh!
- faissaloo 8y agoI haven't had this problem. I wrote a daemon to blend colours for my RGB keyboard in D and it stays below 8192 bytes.
- kristianp 8y agoSee comment about regexes: However, D's compile-time metaprogramming facilities allowed us to get ambitious in some places... for instance, std.uni precomputes some Unicode lookup tables during compilation, and std.regex makes heavy use of metaprogramming to compile regular expression strings to D code, again during compilation. As a result, making use of those features will result in heavier load on the compiler. https://news.ycombinator.com/item?id=18502101 https://news.ycombinator.com/item?id=18502101
- amelius 8y agoNote: in this case "fork" means fork() in the sense of creating a new process, not as in duplicating the source tree.
- dooglius 8y agoI think it is an intentional double entendre
- agumonkey 8y agomy internal confusion wasn't intentional though
- frou_dh 8y ago> duplicating the source tree That reminds me that "fork" when used as a verb on GitHub's UI should more accurately be "cloud clone". GitHub's terminology has muddied the waters between the concept of actual forks (longterm divergent development) and a particular implementation of a permission system for branches.
- chrisseaton 8y agoAs soon as you create your own commits on a clone of the repository you then have a 'fork' in the chain of commits.
- frou_dh 8y agoThat's a second-order observation. We could use any noun for that if and when it's relevant - I suggest alternadoodley. Like I said, "fork" already has a useful meaning with regard to an OSS project, so there's no need to overload it. Is the following sentence not confusing? When you fork on GitHub you create a fork but not every fork is a fork.
- chc 8y agoEvery fork is a fork. They're just not all long-lived or significant, which seems to be the distinction you're drawing here.
- saketmehta 8y agoThe title is hilarious if you read D as "The" and forking as, well, you know.
- w8rbt 8y agoThe first part of this reads like an intro to algorithms class where I think they cover all of these things. Directed graphs, back edges (cycles), convert to a DAG (no cycles), strongly connected components, topological sorting, etc. Nice to see it applied to solve the problem at hand.
- drasah 8y agoيسعي الكثير من الباحثين الي الحصول علي العديد من التقنيات العالية في الجودة منها خدمة توفير الدراسات السابقة الاجنبية التي تدعم الابحاث العلمية http://www.maktabtk.com/services.html http://www.maktabtk.com/services.html http://www.maktabtk.com/ http://www.maktabtk.com/
- szemet 8y agoIt is interesting to use fork() to snapshot application state. It seems so high-level and powerful (Compared to other C/POSIX level stuff - so I'm not comparing it to Scheme/Lisp/"your favorite high/low level environment" here!). We may collect some other examples here - just for fun: - I know that Redis does this (RDB snaphots) too, while the child process saves the actual snapshot, the parent can operate continously relying on the system provided copy on write mechanism - I have also found this: https://github.com/thomasballinger/rlundo https://github.com/thomasballinger/rlundo - It overwrites readline library to get undo function in any REPL using it Other examples?
- chrisseaton 8y agoThere is a time-travelling debugger that forks the process at each statement, allowing you to go back to a previous statement and continue from that point.
- dooglius 8y agoIt seems like forking so often would use up a system's resources very quickly. I'd imagine that each fork needs at least a handful of individual pages for OS bookkeeping overhead, so you'd get into the gigabyte range fast even with perfect copy-on-write.
- chrisseaton 8y agoYes you can't run like that forever. But you could break, step forward and backward and bit, and then resume. I often step forward while debugging, realise that whatever is going wrong has already gone wrong, and would like to step back a few steps.
- caf 8y agoIt's more than a handful of pages - each forked process requires its own set of page tables.
- adtac 8y agoVery interesting. Do you have a link where I can read more about this?
- vectorEQ 8y agothis is very interesting and nice post. thanks! i love this use of fork. it should be obvious from the description of the function that it can be used as such but really never even came to mind. cool!!
- faragon 8y agoAsk Fabrice Bellard to write tdc after tcc [1] :-) [1] https://bellard.org/tcc/ https://bellard.org/tcc/
- reikonomusha 8y agoThis is all so complicated, and reminds me of the joy of doing incremental development in Common Lisp with Emacs and SLIME. Edit-Compile-Run-Repeat cycles feel comparably archaic and slow compared to the much, much shorter and faster EditFunction-RunFunction cycles.
- geokon 8y agoMy only experience is with ELisp/Clojure and you're right that the turn around time is much faster with editing, but at least in ELisp I find "stepping" through code much more confusing. The call stack (or whatever the equivalent is called) has some weird characteristics: 1 - It doesn't match one to one to the code and is in a funky non S-expr form where the function name is outside the parans 2 - As expressions are evaluated and you pop up the stack it will dynamically filled in parts of the higher expression so the "stack" is morphing and changing. It's cool and convenient but also disorienting. 3 - Each line/frame can be horribly long (like a whole let or cond expression in one line) and it's not clear which section/term/subexpression is being called in the frames below I'm using the normal debug-on-entry and I'm definitely no pro, so maybe there is more ergonomic way to debug? (In the little Clojure I've done it seems to be the same)
- reikonomusha 8y agoI believe that this is an artifact of elisp being essentially interpreted, but I could be wrong. With Common Lisp and SBCL, you only see function calls in your stack trace.
- geokon 8y agoGotcha. Thanks. It's probably some issue with my workflow. I'll ask on /r/emacs and see if they give me any tips :)
- WhitneyLand 8y agoNice work thank you for sharing. Tangentially it’s not clear to me what relevance D should have for any greenfield projects where there is not already heavy investment in a code base to consider. First there’s the whole Rust comparison, and then the incredible impact of the comparative size and momentum of ecosystems for various languages. This reddit thread has a few interesting comments. It was quite surprising to see D’s architect/designer discount the value of memory management issues in a sub link there. Anecdotally what I’ve read, and experienced, is that it’s one of the most important sources of bugs when quantity and time to debug and fix are considered. https://www.reddit.com/r/rust/comments/5h0s2n/what_made_rust_more_popular_than_d/ https://www.reddit.com/r/rust/comments/5h0s2n/what_made_rust...
- EvenThisAcronym 8y ago> Tangentially it’s not clear to me what relevance D should have for any greenfield projects where there is not already heavy investment in a code base to consider. Another one of Cybershadow's articles on D that blew my mind is, IMO, one of the greatest arguments for why you should care about D. The beauty, conciseness and flexibility of the implementation here is extremely cool. And this is not a one-off case; there are many programmers in the D community that create awesome stuff like this all the time. Writing in D is like having superpowers, and going back to a less expressive language feels horribly constraining.
- p0nce 8y agoPerhaps are you referring to this article? https://blog.thecybershadow.net/2014/03/21/functional-image-processing-in-d/ https://blog.thecybershadow.net/2014/03/21/functional-image-... Vladimir has one hell of a blog.
- EvenThisAcronym 8y agoYes, thanks. Forgot to actually post the link.
- modeless 8y agoI used this forking trick to speed up the ninja build system too: https://github.com/ninja-build/ninja/pull/1438 https://github.com/ninja-build/ninja/pull/1438 Unfortunately the maintainers didn't like the idea so it won't be merged. But if your project is large enough that ninja takes more than a second to parse your build files every time you build (true for Chromium and Android at least), you might want to try the patch. On the topic of Windows forking, the RtlCloneUserProcess function does exist and it works. The problem is that Microsoft's implementation of the Win32 API keeps state (such as an IPC connection to csrss.exe) that is invalid in the forked process and there's no easy way to clone or reinitialize that state. The child process will run until its next Win32 API call and then probably die. Since almost every Windows program uses Win32 APIs, RtlCloneUserProcess is not useful for forking Windows programs. Microsoft could fix this if they wanted to, at least for a useful subset of Win32. But I imagine it requires a lot of hacking in deep, dark parts of Windows that nobody wants to touch.
- dblohm7 8y agoI have successfully reinitialized enough Win32 in a forked process to be able to throw up a MessageBox, but without source I'd never be able to confidently state that every Win32 call would work correctly.
- modeless 8y agoCool, is your implementation public somewhere? I'd be interested to see it.
- klodolph 8y agoThat’s an interesting note about Chromium, I wonder if it will move at some point to Bazel given that Chromium's latest build script generator GN might be called Yet Another Build System That Looks Suspiciously Like Bazel. (Others: https://www.pantsbuild.org/ https://www.pantsbuild.org/ https://buckbuild.com/ https://buckbuild.com/ https://please.build/ https://please.build/) Obviously this won’t happen unless Bazel adds, like, a million things that Chromium developers think are essential features but still, I wouldn’t be surprised. Bazel already has a ton of developer effort thrown at it to make it work with large code bases well, and recompile large, complicated projects quickly. The forking idea (or at least, the client/server model) is already used by Bazel, and Bazel is capable of managing subprocesses for compiling specific languages. This is how Bazel’s TypeScript support works, for example. When you run Bazel it spawns a server which hangs out in the background, and that server will run a TypeScript compiler in the background. Compiling a TypeScript project with Bazel is noticeably and significantly faster than compiling from the command line, without the hacky / fragile bits that tsc --watch gives you. And obviously none of this would be possible unless the TypeScript compiler were written to heavily cache things and run as a library (see https://youtu.be/f6TCB61fDwY https://youtu.be/f6TCB61fDwY).
- snissn 8y agoI used to use your actionscript3 decompiler, thank you cybershadow!!! It was a great tool :)
- grandinj 8y agoLibreOffice Online also uses a warmed-up-process that forks child processes to execute requests
- bwasti 8y agothere’s a single algorithm (Tarjan’s) that actually solves all your graph needs. It returns a reverse topologically sorted DAG of strongly connected components
- CyberShadow 8y agoYes, but I need to sort by two criteria, and Kosaraju's algorithm is simpler to implement :)
- kardos 8y agoWhat would be involved to make ccache [1] support D? [1] https://ccache.samba.org/ https://ccache.samba.org/
- jon889 8y agoI understood it up to "Note how the compilation order is the reverse of the topological order (we’ll get back to this in a bit)." But then couldn't find where you got back to it, and can't quite understand why it's the reverse of the topological order or how that's possible?
- tpxl 8y ago>can't quite understand why it's the reverse of the topological order For example: A depends on B depends on C, so the graph is A->B->C. To compile A, first B must be compiled, and for B, C must first be compiled. The compilation order has to be in reverse of the dependency graph. >how that's possible? The compiler first determines dependencies and then compiles. The compilation then happens per file, so that part is trivial.
- AndyKelley 8y agoImpressive demo and lovely writeup. That was fun to watch. I've been working on building the Zig self-hosted compiler this way from the ground up, except with reference counting the cached stuff rather than using fork(). This lets me do the caching at the function level, even more fine grained than the file level. Here's a 1min demo: https://www.youtube.com/watch?v=b_Pm29crq6Q https://www.youtube.com/watch?v=b_Pm29crq6Q
- p1necone 8y agoDid anyone else read this title as "D compilation is too slow and I am forking the compiler (in source control because I think I can do a better job writing it)"?
- nineteen999 8y agoEverybody thought that until they read the article, which was clearly the intention of the author.
- petre 8y agoIt's comparable to go, maybe a bit slower. In comparison to DMD or LDC, rustc feels like endlessly grinding. I haven't used GDC.
- anticensor 8y agoThe original author of D is suprisingly missing from conversation.
- WalterBright 8y agoWalter's D9000 computer is monitoring this thread in his stead.
- MaxBarraclough 8y agoNot polling, I trust. Hacker News threads: like Hacker News fibers, but less cooperative.
- WalterBright 8y agoBack in the 1970's, I was fascinated by the (now famous) ADVENT game and how it worked, so I studied the Fortran source code. When started up, it would do all kinds of slow (at the time) initialization of its data structures. Then the genius move kicked in - it saved the memory image to disk as the executable file! Next time it ran, it was already initialized and started up instantly. It blew my mind. I liked the idea so much, that years later when I worked on the text editor I use (MicroEmacs), I did the user configuration the same way. Just change the global variables, then patch the executable file on the disk with the changed values. It was so, so much simpler than defining a configuration file, serializing the data, writing/reading the file, and deserializing it. It worked especially great on floppy disk systems, which were incredibly slow. But then came viruses, malware, etc. Patching the exe file became a huge "malware alert", and besides, Microsoft would mark the executable as "read only" while it was running. Too bad.
- wging 8y agoGNU Emacs does a similar-sounding trick in its build process (called 'dumping' / 'unexec'), but not at runtime. https://lwn.net/Articles/707615/ https://lwn.net/Articles/707615/ Come to think of it, I think there are applications to my own work... I'd have to be careful, though.
- caf 8y agoIf you're looking at implementing something along those lines these days, take a look at CRIU: https://www.criu.org/Main_Page https://www.criu.org/Main_Page
- nicoburns 8y agoIt seems like someone should come up with an "executable+data storage" file format (where virus scanners can know to only check changes in the executable section) Maybe they can make one that is supported cross platform while they're at it...
- qwerty456127 8y agoI wish somebody would fix the GCC/G++ this way. I was stupid enough to try installing webkitgtk from aur (as I couldn't find what binary Arch package would make it work in Python), many hours have already passed, I have already written the program I wanted with Qt instead of Gtk while waiting (although the whole computer works annoyingly slowly during the process) and it still is compiling...