9 ms·
A fun optimization trick from rsync
- ThePhysicist 8y agoAndrew Tridgell’s thesis is also a very interesting read, as rsync has some pretty innovative algorithms that make the file transfer and remote diffing fast: https://rsync.samba.org/~tridge/phd_thesis.pdf https://rsync.samba.org/~tridge/phd_thesis.pdf
- toolslive 8y agoSome compilers turn large switches into lookup tables. Using side effects like this however, makes the compiler shy away from this optimisation, and compile it literally. So it's probably not a good idea anymore.
- ygra 8y agoI'm not sure switch performance is a relevant concern for setting the last modification time of a file.
- OskarS 8y agoSo, slightly off topic, but one thing from C that I really miss in other languages is subroutine-local static variables. It always annoys me in Java or C# that you can't really make a static variable that's scoped to a single method or function, you have to scope them to the entire class. It's common enough that a private static variable is only needed in a single method or function, so why not do it the way C does it?
- VMG 8y agoIn js you can use `this.x` or `this.methodname.x`
- waingake 8y agoI'd be interested if someone could show me a FP friendly solution to this problem.
- jbverschoor 8y agoSo without actually looking into anything. What id you have a directory structure which is built out of 2 mounts. One local fs and one network mounted. Then lets say method 5 works on one, and method 1 works on the other, both are the only ones that work. Then it would basically fail, depending on the order of directories enumerated, eventhough there is a supported method.
- de_watcher 8y agoI haven't looked at the code, but the ENOSYS error is more about the capabilities of the kernel. So when we eventually start swapping entire kernels at runtime then it'll break.
- ecma 8y agoThanks, I hate it. I'm a bit bemused about this bizarro case_N.h trickery. I'm also almost positive __COUNTER__ would be adequate and entirely remove the need for __LINE__ as suggested in the addendum which is likely to be quite large in any non-trivial source unit. I mean, something gcc this way comes I guess...
- scatters 8y ago__COUNTER__ is not standardized. Repeated inclusion is.
- bacon_waffle 8y agoEdit: d'oh - I misread, the addendum is doing exactly this... I don't understand the need for the macro-fu to generate the case values. The use of switch_step++ in each previous case seems to drive that, but couldn't the same be accomplished by setting switch_step to a constant? static int switch_step = 0; switch(switch_step) { // Falls through between cases default: #if METHOD_0_AVAILABLE switch_step = 0; case 0: if (method_0_works(...)) break; #endif METHOD_0_AVAILABLE #if METHOD_1_AVAILABLE switch_step = 1; case 1: ... }
- netheril96 8y agoSo thread unsafe?
- usefulcat 8y agoDefinitely
- tropo 8y agoIt doesn't have to be. It just is, because there is no need for the overhead of dealing with threads.
- romed 8y agoNote that if this were C++ (11 or later) this could be done with the static variable in a thread-safe way, since function-scoped static variables initialized by functions are guaranteed to be initialized exactly once. So this code could be something like: int set_the_mtime(...) { static int starting_from = set_mtime_starting_from(0); set_mtime_starting_from(starting_from); } // Try various ways of setting mtime until it works. int set_mtime_starting_from(int starting_from) { // horrible switch statement }
- repsilat 8y agoIn C++ you could also make an object (per thread?) and use member vars instead of static vars. Also, if you're going to use static vars in multithreaded contexts doing this, better to write thing = 5; (via that macro magic) than `thing++`. Then at least nothing too bad should happen...
- matthewaveryusa 8y agoThat's not clever, that's language abuse and horrific -- You could do this in so many other ways there is absolutely no point in abusing #includes mid-source-code (without mentioning the code smell around statics.) Now, as a working curiosity, this is pretty damn cool.
- nwmcsween 8y agoNot really its just a static var on a switch statement nothing really bad about it, in fact its a semi nice way to handle a simple state machine.
- repsilat 8y agoNot tooo uncommon either. It's a "reasonable" way to write generators in C (if you're masochistic Python programmer, I guess.) Switch on the last return point at the top of the function, and make all variables that need to persist between calls `static`. (I've written it before, and I swear I didn't invent it... Maybe it's just a short skip from Duff's Device? Still, using it to pick up before the last return instead of after is new trick for me!)
- geezerjay 8y agoTo my eyes it also looked like a Duff's device which kept track of the successful state.
- Piskvorrr 8y agoYup. First thing that popped into my mind - with Duff's observation following shortly thereafter. Clever...too clever by half, IMNSHO.
- fpoling 8y agoThis was modeled on early Fortran where all local variables were static and it was trivial to implement persistent state machines.
- 8y ago
- usefulcat 8y agoAn interesting trick, but it seems like there would be a simpler way, like having set_the_mtime be a function pointer. Initially it would point to an implementation that figures out which method works and sets the function pointer to point to a particular implementation.
- ychen306 8y agoIt's more inliner-friendly this way though.
- megous 8y agoNo. Compiler can't assume value of switch_step at compile time, so it would have to inline the whole horrid thing every single time.
- beefsack 8y agoSounds really clever, but also has the potential to be really opaque and confusing. On the other hand, the trick in the article is quite verbose. Can be tricky balancing terseness with readability.
- Sharlin 8y agoI would say that this switch hack is lightyears more "clever" (that is, opaque and confusing) than a simple function pointer.
- usefulcat 8y ago> has the potential to be really opaque and confusing Yes, but.. compared to switch and preprocessor hacks described in the article? Granted it's subjective but I'd find a function pointer that's assigned to once to be way easier to comprehend.
- carlmr 8y agoYeah, I think both methods are somewhat opaque, and the one described here is opaque + hacky. I wouldn't let this through code review.
- vortico 8y agoI don't like it. You should put the logic where the logic should be, so it's clear to see what was intended. typedef int (*MethodFunc)(); void doMethod() { static int methodId = 0; static const MethodFunc methodFuncs[] = { #ifdef METHOD_1_CAN_COMPILE method1, #endif method2, ..., NULL }; while (methodFuncs[methodId]) { int success = (methodFuncs[methodId])(); if (success) return 0; methodId++; } return -1; }
- blux 8y agoIn case performance is all you are after, this has much less potential for inlining than the rsync implementation has.
- vortico 8y agoTrue, but for rsync's case of setting the mtime of a file, performance of this logic is utterly insignificant.
- bayindirh 8y ago"Everything is fast for small n." -Knuth. While syncing some million files, I'm sure it'll have an impact tho. P.S.: Yes, we use it for a million files, regularly.
- blibble 8y agoit's probably not noticeable for a million files the syscall is going to be many, many orders of magnitude slower than the difference between a direct and an indirect call
- vortico 8y agoWith trivial method() functions, you could speed through that loop a million times in a millisecond.
- 8y ago
- Jedd 8y agorsync is an amazing tool, full of delightful secrets. One thing it doesn't have natively (unless it's really well hidden) is the ability to look at two directory structures, and generate a delta of the two out to a separate location (say a USB stick). A very useful feature for backups where you've got good enough (to run an rsync --dry-run) network connectivity, but not good enough to actually do the transfer.
- rstuart4133 8y agoUnless you actually want whole files stored in a directory tree on your USB, --only-write-batch does exactly that. From the man page: you can feel free to write the batch directly to some portable media
- Jedd 8y agoWow .. how long has that been there? (Sadly it's clear it was in fact there long before I wrote a workaround in response to not finding it.)
- lazylizard 8y agocan rsync --dry-run and | output to a file?
- Jedd 8y agoYup, that's what I ended up doing [1] - but was mildly surprised it wasn't built in, and very surprised that I couldn't find anyone else's solution. [1] https://jeddi.org/b/2016/05/28/rsync-from-a-to-b-via-usb/ https://jeddi.org/b/2016/05/28/rsync-from-a-to-b-via-usb/
- akvadrako 8y agoI think he means a diff that includes the differences in content.
- alecbenzer 8y agoAwesome, that's horrifying. One concrete issue with this technique: it doesn't "loop". Meaning, for example, if initially method #3 doesn't work but method #4 does, it'll settle on method #4. If later, method #3 starts working, it won't switch it. Worse, if method #4 stops working, it'll just always fail. I imagine this isn't an issue for rsync's use but could be a concern if applying it more generally.
- eridius 8y agoAccording to the article, a step isn't skipped because it had a transient failure, it's skipped because it returns a special error code ENOSYS that means the syscall hasn't even been implemented, and therefore there's no point in ever trying it again.
- vortico 8y agoJust remove the `static` keyword and there you go. But it's an "optimization", and avoiding previously attempted methods is the whole point of the trick. Otherwise it would be an easy and uninteresting function.
- lazyjones 8y ago> Just remove the `static` keyword and there you go. That‘ll probably try all methods on every single file that is processed, so if method #16 is the one that works, you get 15 unnecessary syscalls for every file.