4 ms·

"Even on very large C++ project like Chrome, there's no reason why incremental updates should take more than 1-2ms. If all you're doing is changing a single fun

"Even on very large C++ project like Chrome, there's no reason why incremental updates should take more than 1-2ms. If all you're doing is changing a single function in the binary file, why do our linkers rewrite the whole thing" Because it requires N^3+ dataflow problems to track what is possibly changed with significant accuracy.

josephg 7y ago
Does it? Let’s say I edit a function, and my editor (attached at the hip to my compiler) knows which bytes have been changed. So it knows my change was isolated to a function in a .cpp file. The compiler has cached the compilation environment from the last build, and with that in mind it could recompile just this one function. Then we need to binary patch the function - which essentially requires allocating disk space inside the binary executable. If the previous compiler pass left some free space, we could allocate out of that and mark the old function memory as reusable. Then we need to update CALL pointers - either store them in a list or have every function do indirect calls through a table, and then you just need to update the table entry. If you want to get fancy you could do better than function level granularity, but I think that alone would give us sub-ms builds. I wouldn’t want to change the process for release builds - but for incremental debug builds I don’t see where you’re getting an N^3 from.
- DannyBee 7y ago
  Yes, it does. "The compiler has cached the compilation environment from the last build, and with that in mind it could recompile just this one function." First, this is actually the most trivial possible case, and even there, as you'll see, this is not correct. Outside of a function it does not handle changing types, changing access permissions in classes, changing between virtual and non, etc. It does not handle changing globals, things with attributes of various sorts, etc. All of those require understanding the uses, or overestimating them. As for whether function-local changes can have non-local effects, the answer is flatly "yes". You don't even have to be that creative, since you can do things like force template function output and other things that affect global state from a function in C++. The assumption that because i changed text in one function, it means the possible changes are limited to that function, is not correct in C++ :) There are languages in which it is, mind you, just C++ is 100% not one of them. Honestly, I would strongly suggest you start to read papers on this, this is an incredibly well studied area, and the costs are well known. If it was easy and cheap, we'd still be doing it ;) It used to be a pretty standard feature of editing environments for things like LISP, etc.
  - josephg 7y ago
    Do you have any recommendations for places to start reading? I didn't realise it was a well studied area - naively it seems like it would be possible in many languages. It would certainly be trivial for 90% of the transpiled / polyfilled stuff that we do in modern typescript / javascript. I completely agree that doing this to live-update an optimized build would extremely expensive and difficult. And I'll happily acknowledge that (for example) adding or moving fields in a struct would be hard to implement. But adding a compiled specialization of a template function / class should be "easy" to handle. Its non-local, but I can imagine a dependancy tree of functions needed for the compilation. On update, we can figure out a diff of that tree, free all the now-unused function bodies in the binary and then add (compiling if necessary) all the added / updated functions. C++ might be one of the worst languages to implement this for - .NET, JVM, typescript or Go might all be much easier. But yeah, if this has been extensively looked in to I'd love to learn why we don't do it for modern development. It seems like an obvious win, and if we don't do it I hope its for good reasons.

josephg 7y ago

Does it? Let’s say I edit a function, and my editor (attached at the hip to my compiler) knows which bytes have been changed. So it knows my change was isolated to a function in a .cpp file. The compiler has cached the compilation environment from the last build, and with that in mind it could recompile just this one function. Then we need to binary patch the function - which essentially requires allocating disk space inside the binary executable. If the previous compiler pass left some free space, we could allocate out of that and mark the old function memory as reusable. Then we need to update CALL pointers - either store them in a list or have every function do indirect calls through a table, and then you just need to update the table entry. If you want to get fancy you could do better than function level granularity, but I think that alone would give us sub-ms builds. I wouldn’t want to change the process for release builds - but for incremental debug builds I don’t see where you’re getting an N^3 from.

DannyBee 7y ago
Yes, it does. "The compiler has cached the compilation environment from the last build, and with that in mind it could recompile just this one function." First, this is actually the most trivial possible case, and even there, as you'll see, this is not correct. Outside of a function it does not handle changing types, changing access permissions in classes, changing between virtual and non, etc. It does not handle changing globals, things with attributes of various sorts, etc. All of those require understanding the uses, or overestimating them. As for whether function-local changes can have non-local effects, the answer is flatly "yes". You don't even have to be that creative, since you can do things like force template function output and other things that affect global state from a function in C++. The assumption that because i changed text in one function, it means the possible changes are limited to that function, is not correct in C++ :) There are languages in which it is, mind you, just C++ is 100% not one of them. Honestly, I would strongly suggest you start to read papers on this, this is an incredibly well studied area, and the costs are well known. If it was easy and cheap, we'd still be doing it ;) It used to be a pretty standard feature of editing environments for things like LISP, etc.
- josephg 7y ago
  Do you have any recommendations for places to start reading? I didn't realise it was a well studied area - naively it seems like it would be possible in many languages. It would certainly be trivial for 90% of the transpiled / polyfilled stuff that we do in modern typescript / javascript. I completely agree that doing this to live-update an optimized build would extremely expensive and difficult. And I'll happily acknowledge that (for example) adding or moving fields in a struct would be hard to implement. But adding a compiled specialization of a template function / class should be "easy" to handle. Its non-local, but I can imagine a dependancy tree of functions needed for the compilation. On update, we can figure out a diff of that tree, free all the now-unused function bodies in the binary and then add (compiling if necessary) all the added / updated functions. C++ might be one of the worst languages to implement this for - .NET, JVM, typescript or Go might all be much easier. But yeah, if this has been extensively looked in to I'd love to learn why we don't do it for modern development. It seems like an obvious win, and if we don't do it I hope its for good reasons.