3 ms·

"This is very nice in theory, but in practice you can only do it in assembly language, because no commonly used high level language supports the coroutine call

"This is very nice in theory, but in practice you can only do it in assembly language, because no commonly used high level language supports the coroutine call primitive." I think you can get a similar effect in a high-level language by transforming the logic inside your normal function into a state machine that effectively runs one line logical line of code per call. You still end up with a call stack, but you don't use it the same way. I'm currently implementing an approximate search engine this way in a high level language. I've done some proof-of-concepts with this technique and it seems very efficient, because I can just kill the machines without having to run them to completion when I think I've found my answer (or am sure there's no answer to find).

lukesandberg 16y ago
yeah but isn't doing this state machine transformation pretty complicated? i know that this is what C# does to implement its iterator blocks, but they have the compiler write the state machine for you. Do you think that this is practical as a general solution in a language that doesn't provide these tools for you?
- bsaunder 16y ago
  Fair point. Getting to that "a ha!" moment when I figured out that this would help (a lot) was very hard. Forcing my code to behave that way was definitely non-intuitive and challenging. Having merely gotten it working and proving my theory (it works) that it's a huge efficiency gain, I now get another crack at the next version. I don't think it's necessary for a compiler to do the work for you, or to have it built in as a fundamental feature of a language (that certainly helps). But I do agree that without a library or (dare I say) framework, it is a bit challenging to code from scratch. Probably the hardest part (for me), is that it breaks so many fundamental notions of programming. One obvious feature that I'm making heavy use of is that I can get data out of the state machine on every call (that's almost the whole point for me). I can use that data and determine if I want to call it any more or just kill it (or maybe put it aside to get called later). Perhaps more interesting, I have the opportunity to pass data into the state machine on every call down to it (not just on the initial call). That seems powerful. I already have an idea on how to utilize that. I do agree, that at some point this technique would be more efficient if implemented in assembly than in a high-level language. My approach is probably similar to implementing a binary search in a high-level language and comparing it so a linear search in C. At this point I'll take the flexibility of the high-level language. Almost certainly a lower level implementation of the same pattern would kick butt.

lukesandberg 16y ago

yeah but isn't doing this state machine transformation pretty complicated? i know that this is what C# does to implement its iterator blocks, but they have the compiler write the state machine for you. Do you think that this is practical as a general solution in a language that doesn't provide these tools for you?

bsaunder 16y ago
Fair point. Getting to that "a ha!" moment when I figured out that this would help (a lot) was very hard. Forcing my code to behave that way was definitely non-intuitive and challenging. Having merely gotten it working and proving my theory (it works) that it's a huge efficiency gain, I now get another crack at the next version. I don't think it's necessary for a compiler to do the work for you, or to have it built in as a fundamental feature of a language (that certainly helps). But I do agree that without a library or (dare I say) framework, it is a bit challenging to code from scratch. Probably the hardest part (for me), is that it breaks so many fundamental notions of programming. One obvious feature that I'm making heavy use of is that I can get data out of the state machine on every call (that's almost the whole point for me). I can use that data and determine if I want to call it any more or just kill it (or maybe put it aside to get called later). Perhaps more interesting, I have the opportunity to pass data into the state machine on every call down to it (not just on the initial call). That seems powerful. I already have an idea on how to utilize that. I do agree, that at some point this technique would be more efficient if implemented in assembly than in a high-level language. My approach is probably similar to implementing a binary search in a high-level language and comparing it so a linear search in C. At this point I'll take the flexibility of the high-level language. Almost certainly a lower level implementation of the same pattern would kick butt.