Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

What I learned from my first C coding challenge

blog.jasonmooberry.com

Post reply on HN
Print view View original

31–40 of 85 posts

Re: What I learned from my first C coding challenge

#31

Post by tptacek »

Xuzz wrote: post #27
tptacek wrote: post #22

Earlier quoted context omitted.

Sure. The flaw here isn't strcmp. In fact, most crypto compares don't use strcmp, even in naive code; an HMAC-SHA1 MAC, for instance, is an array of 8-bit bytes, not the hex string that programs encode them into for human consumption. "memcmp" is the normal culprit. Timing attacks aren't a flaw in memcmp or strcmp. Touching every byte of a string is stupid behavior in the overwhelming majority of cases.

Unless, of course, you're Nintendo: http://wiibrew.org/wiki/Signing_bug

Good find. Again, notice how the problem here isn't strcmp or it's timing behavior; it's mistakenly using ASCIIZ strings to hold ciphertext.

Re: What I learned from my first C coding challenge

#32

Post by binarycrusader »

(I realise the poster came up with a different solution ultimately, but this bears repeating.)

Don't hand-roll standard library functions. You'll very likely regret it later.

In particular, as hardware advances, OS vendors often update their implementations with optimisations specific to new hardware platforms. This both allows improvements for all programs that consume those interfaces, and prevention of regressions when hardware changes in some cases.

In addition, you really don't want to be the one that introduces a security bug into your program because it turns out your optimisation work didn't account for a scenario that the standard library function does.

I'm aware that there may be cases where some believe it's appropriate; don't give into temptation. It's a bad idea to duplicate the standard library.

Re: What I learned from my first C coding challenge

#33

Post by jefffoster »

T-hawk wrote: post #12
jamesaguilar wrote: post #2

I'm trying to picture a non-synthetic program where normalizing a URL is a significant part of the inner loop and I'm drawing a blank. Can someone help me out?

Here's a similar case: Ranking of poker hands. That can involve many of the same steps, like sorting a small list of inputs (5 or 7 cards) into a normalized configuration (three-of-a-kind is represented as AAABC where B > C) and taking a hash to memoize the result. And you sure might want that in a tight inner loop if you're writing a poker simulator or AI where you want to crunch a few billion iterations.

Actually, for a poker hand evaluator the last thing you want to do is sort the hands. There's a small enough number of unique card combinations that you can arrange it so that you look up in pre-computed tables more often than not.

One clever trick is assigning a prime to each card value. By multiplying the values together you get a unique number representing each hand without needing to sort.

There's a great description of an algorithm at http://www.suffecool.net/poker/evaluator.html.

Re: What I learned from my first C coding challenge

#34

Post by mlvljr »

icefox wrote: post #29

Any more detailed information about the coding challenge? For example the repo references a 5Murls.txt file, but it isn't part of the repo and the blog says it needs to "output in a standardized format:", but doesn't specify what "standardized" means nor does the current code actually output anything (the printf is disabled). Does it specifically need to go to stdout or just that it exists somewhere in memory? Does i…

Second that. The author could link to all relevant tests/specs as well, if he links to his implementation [of what?] code.

Re: What I learned from my first C coding challenge

#35

Post by csense »

tsahyt wrote: post #28

It's interesting that he points out that testing for zero is cheaper than comparing two numbers. Interesting because this might not always be the case. For a quick test I used the conditions (i=0; i And this is where it gets complicated. This optimization depends entirely on the inner workings of the ALU. Theoretically one can test against zero with just one subtraction, because 0-n == n-0 is always true, whereas a-b…

The second version (test against zero) benefits from the fact that the subtraction instruction sets the Z flag automatically. So the end of the second loop is something like "sub i,1" followed by "jnz top".

The most straightforward implementation of first loop would be "add i,1" followed by "cmp i,NUMBER" followed by "jb top" (or "jl top" if i is signed). It's an extra instruction which may be even slower, depending on specific CPU and surrounding code, if NUMBER is a literal or memory access (as opposed to register value).

My guess is that your compiler will produce code that takes advantage of the savings if you turn on optimizations, but you might have to actually do something in the body of the loop to keep the compiler from optimizing the loop completely out (or tweak flags to enable/disable specific optimization techniques). Adding a loop body will make the timing difference less noticeable, as the single-instruction savings of the zero-test version becomes a smaller percentage of the total time per iteration.

Disclaimer: This is how I'd write assembly by hand. A compiler could conceivably do something quite different, depending on the specific application code, compiler, version and flags. I also haven't yet taught myself 64-bit x86 assembly code, although I understand it's rather similar to 32-bit x86 with more registers available.

Re: What I learned from my first C coding challenge

#36

Post by tsahyt »

csense wrote: post #35
tsahyt wrote: post #28

It's interesting that he points out that testing for zero is cheaper than comparing two numbers. Interesting because this might not always be the case. For a quick test I used the conditions (i=0; i And this is where it gets complicated. This optimization depends entirely on the inner workings of the ALU. Theoretically one can test against zero with just one subtraction, because 0-n == n-0 is always true, whereas a-b…

The second version (test against zero) benefits from the fact that the subtraction instruction sets the Z flag automatically. So the end of the second loop is something like "sub i,1" followed by "jnz top". The most straightforward implementation of first loop would be "add i,1" followed by "cmp i,NUMBER" followed by "jb top" (or "jl top" if i is signed). It's an extra instruction which may be even slower, depending…

The compiler optimizing out the loop completely is one of the reasons why I didn't turn on optimizations here, although there was a loop body. gcc is smart enough to optimize loops with a fixed outcome away in some cases. I probably should have written a more complex loop body.

That said, it's very likely that the compiler will make sense of such an optimization and produce the quicker assembly code like you just wrote it.

What I wanted to say with my post was really that things like these are heavily depended on architecture and that comparisons could be optimized in hardware.

Re: What I learned from my first C coding challenge

#37

Post by bradleyjg »

jamesaguilar wrote: post #2

I'm trying to picture a non-synthetic program where normalizing a URL is a significant part of the inner loop and I'm drawing a blank. Can someone help me out?

They want to use a normalized URL as the hashkey to cache system.

Depending on exactly what type of hashing they are doing, the normalization could be a significant fraction of the lookup time.

If you are going to get all micro-optimized, you should probably combine the normalization and hash steps, as there is likely some string parsing / building that could be eliminated.

Also: it's a pretty fun exercise.

Re: What I learned from my first C coding challenge

#38

Post by exDM69 »

binarycrusader wrote: post #32

(I realise the poster came up with a different solution ultimately, but this bears repeating.) Don't hand-roll standard library functions. You'll very likely regret it later. In particular, as hardware advances, OS vendors often update their implementations with optimisations specific to new hardware platforms. This both allows improvements for all programs that consume those interfaces, and prevention of regressions…

Your advice is good but a bit too generalized here.

The reason why the standard library functions, qsort in particular, were performing worse in this case is not related to the implementation to the functions themselves. Instead, it is because adding a function call to a foreign function will practically inhibit all compiler optimizations that can happen around the call site. So the "overhead" of the function call itself is a lot more expensive than differences in the function implementation itself. In the case of qsort with function pointer callbacks, the effect is especially devastating. Benchmark qsort vs. C++ std::sort to see how much (a lot).

So when writing performance critical C code, it's a perfectly good option to re-write a standard library function, especially a simple one like this. Make it an inline function in a header file to make sure the compiler can optimize.

If your compiler can do link time optimization to these function calls, then you don't have to re-write them. Before LTO becomes mainstream, sometimes you might have to.

Re: What I learned from my first C coding challenge

#40

Post by exDM69 »

tsahyt wrote: post #36
csense wrote: post #35

Earlier quoted context omitted.

The second version (test against zero) benefits from the fact that the subtraction instruction sets the Z flag automatically. So the end of the second loop is something like "sub i,1" followed by "jnz top". The most straightforward implementation of first loop would be "add i,1" followed by "cmp i,NUMBER" followed by "jb top" (or "jl top" if i is signed). It's an extra instruction which may be even slower, depending…

The compiler optimizing out the loop completely is one of the reasons why I didn't turn on optimizations here, although there was a loop body. gcc is smart enough to optimize loops with a fixed outcome away in some cases. I probably should have written a more complex loop body. That said, it's very likely that the compiler will make sense of such an optimization and produce the quicker assembly code like you just wro…

> The compiler optimizing out the loop completely is one of the reasons why I didn't turn on optimizations here

Use a non-constant value for the loop and put a dummy load inside to stop compiler from doing loop unrolling and/or dead code elimination.

I often use time(), rand() or even argc to get dummy values when looking at assembly from compiler optimizations.

Post reply on HN