211–220 of 249 posts
Earlier quoted context omitted.
I believe the first `jne` should be `je`, right ?
No, the assembler is correct. Jump (early) back to the beginning of the loop if not equal to s; otherwise, continue executing the next instruction (add eax, 1) and then unconditionally jump back to the beginning of the loop.
How fast is forth compared to C these days?
People say that forth isn't very optimisable for our register machines, but I reckon that you can get pretty good results with some clever stack analysis. It's actually possible to determine arity statically if you don't have multiple-arity words, which are very rare. That allows you to pass arguments by register.
Anyway, I'm not even close to an expert so don't take what I said as facts.
Earlier quoted context omitted.
Neat! Although you'll need to make a copy of `n`. The second loop will reduce the value of n to null. Edit: Also, there's an off by one error. should be: #include #include int run_switches(const char *s, const size_t n) { int res = 0; uint8_t tmp = 0; for (int i = n & 127; i--; ++s) tmp += *s == 's'; res += tmp; for (int size = n >> 7; size--;) { tmp = 0; for (int i = 128; i--; ++s) tmp += *s == 's'; res += tmp; } re…
Replying to my own post: The off by 1 error was incorrect. It's because I was calling the function wrong. I had been giving it the size of the buffer, not the size of the string. Also, someone else figured out that we can just use an and instruction instead of cmp. That gives us this version: #include #include int run_switches(const char *s, const size_t n) { int res = 0; uint8_t tmp = 0; for (int i = n & 127; i--; +…
Earlier quoted context omitted.
True, but independently of whether "cmov rax, ..." or "jnz L; mov rax, ...; L:" is used, subsequent instructions that reads rax needs to stall until rax has been written to (or at least until cmov/mov has executed if bypasses are used).
The difference is that in the case where the condition is false and predicted false the jump variant will not delay if the value being moved into rax is delayed, the cmov variant will. Effectively that value becomes a false dependency. As best I can tell this case is rare enough that one shouldn't generally be afraid of cmov, and probably compiler authors should consider using it more frequently. What one shouldn't d…
Earlier quoted context omitted.
Indeed. I suppose the two lessons are, stick with C, and don't forget the semantics of your original problem when optimizing. int run_switches(const char *s) { int res = 0; uint8_t tmp = 0; size_t n = strlen(s); for (size_t i = n & 127; i--; ++s) tmp += (*s == 's'); res += tmp; for (size_t j = n >> 7; j--;) { tmp = 0; for (size_t i = 128; i--; ++s) tmp += (*s == 's'); res += tmp; } return 2 * res - n; }
This makes the assumption that the only characters in the string are "s" and "p". There is no basis for this assumption. I think this code solves a different problem rather than being an optimisation of the original code.
Earlier quoted context omitted.
To a point . A modern C compiler generates mind boggingly fast assembler. However, some languages make it way easier to write sophisticated algorithms more easily. For instance, suppose you're writing a program to find the nth Fibonacci number for whatever reason. In Python, the naive version might look like: def fib(n): if n On my machine, that takes about 12 seconds to find the 40th number. Altering that slightly l…
adding @cache meaningfully changes the algorithmic complexity from O(1.8^^N) (iirc - it's obviously exponential) to O(N).
Earlier quoted context omitted.
True, but independently of whether "cmov rax, ..." or "jnz L; mov rax, ...; L:" is used, subsequent instructions that reads rax needs to stall until rax has been written to (or at least until cmov/mov has executed if bypasses are used).
The difference is that in the case where the condition is false and predicted false the jump variant will not delay if the value being moved into rax is delayed, the cmov variant will. Effectively that value becomes a false dependency. As best I can tell this case is rare enough that one shouldn't generally be afraid of cmov, and probably compiler authors should consider using it more frequently. What one shouldn't d…
Earlier quoted context omitted.
I'm not a compiler expert but if it's a "very simple loop" is it still too complex for the compiler to make good machine code? Did they use a bad compiler on purpose? Or are computers just not yet fast enough to do a good job with very simple loops in practical compilers?
> are computers just not yet fast enough to do a good job with very simple loops in practical compilers? The short answer to this question is 'yes', but there are some extenuating factors: - Although we could do interesting things with unlimited computational resources, the current crop of c compilers is simply not very good, compared with what's possible today. - Performance is always workload-dependent; the compile…
That's quite dismissive. What exactly "is possible today" and why aren't these top compilers using them?
Earlier quoted context omitted.
No, the assembler is correct. Jump (early) back to the beginning of the loop if not equal to s; otherwise, continue executing the next instruction (add eax, 1) and then unconditionally jump back to the beginning of the loop.
well then there's a magical bit somewhere since both assembly listing are identical
There's nothing "magical" about paying attention before condescending to someone.
A clickbait title for an in-depth look at hand-optimizing a very simple loop.