What I learned from my first C coding challenge • Hacker News Board

Re: What I learned from my first C coding challenge

#81

Post by gsg » Wed, Sep 05, 2012, 3:15 PM UTC

alexkus wrote: post #75

gsg wrote: post #73

Earlier quoted context omitted.

How is testing for a terminator the right approach? The comparator is only supposed to look at a single parameter, and the only null byte in the url string is at the end...

Both implementations have exactly the same outcome for all inputs, it's just one has less code (well, code that is less complex) inside the loop and therefore is more pipeline friendly and/or just executes faster. Yes the string comparator is comparing items like: "a=3&a=4" and "a=4" but it doesn't really matter since it'll never put such items in the wrong order. It's a quirk of passing the original url as 'const ch…

I'm aware that it will return the right answer, but I was worried that it may look at too much of the url string in order to do so.

Consider the (admittedly perverse) input "test.php?a=1&a=1&a=1&a=1&a=1". At each comparison, the comparator you suggest will look at the entire remaining part of the string.

Maybe duplicate elements are considered invalid input and aren't a concern, I'm not sure. But fixing it is not hard and doesn't require fiddling about with copying strings or adding terminating nulls: just find and remember the parameter length once, and use a length-based comparator.

Re: What I learned from my first C coding challenge

#82

Post by alexkus » Wed, Sep 05, 2012, 5:26 PM UTC

gsg wrote: post #81

alexkus wrote: post #75

Earlier quoted context omitted.

Both implementations have exactly the same outcome for all inputs, it's just one has less code (well, code that is less complex) inside the loop and therefore is more pipeline friendly and/or just executes faster. Yes the string comparator is comparing items like: "a=3&a=4" and "a=4" but it doesn't really matter since it'll never put such items in the wrong order. It's a quirk of passing the original url as 'const ch…

I'm aware that it will return the right answer, but I was worried that it may look at too much of the url string in order to do so. Consider the (admittedly perverse) input "test.php?a=1&a=1&a=1&a=1&a=1". At each comparison, the comparator you suggest will look at the entire remaining part of the string. Maybe duplicate elements are considered invalid input and aren't a concern, I'm not sure. But fixing it is not har…

True, and it's a simple change to stop the comparison at either a NUL or a '&', so that it doesn't that extra unnecessary time.

The other two improvements I'd be looking to do are:

1) try to rework the insertion sort to make it use a binary search (if over a certain threshold that is yet to be determined by experimentation). Should be faster than looping through each element each time.

2) Not automatically extend the tail each time (where insertion somewhere between head and tail is required). The element being added may be one from the head so it's best to work out where it goes first and then pick the extension direction that requires the fewest number of elements to be shuffled up. Also the shuffling can be done in bulk using memmove() (can't use memcpy since the areas of memory will overlap when shuffling up by more than one position); this should also be faster than doing them one at a time.

Anyway, i'm off on holiday so I've got about another 15 minutes to look at this so I'm not going to get far. If I remember I'll try and check up on the status of it in github when I get back.

Re: What I learned from my first C coding challenge

#83

Post by alexkus » Wed, Sep 05, 2012, 5:27 PM UTC

tedunangst wrote: post #57

alexkus wrote: post #46

Good work, one obvious speed up is, if possible, removing the use of dynamic memory. Simply supply a static output buffer to url_sort so that it doesn't have to allocate/free memory for the resulting URL. That took my execution for 5M lines of (not really representative but it's all I could be bothered to sort out at 11pm): /test.php?b=b&c=bb&a=3&a=4 down from 5.05s to 4.49s (so down 10%) on an old 1.5GHz Athlon Linu…

// comments and mid-function variables are C99 standard. The platforms that don't support them are probably not worth supporting yourself, and are not likely to be seen running varnish. This is the same mindset that held mozilla back for ages and ages because the hpux compiler from 1987 didn't support some c++ feature, so therefore nobody was allowed to use it even in 1997.

True, but not using // comments and mid-function variables is not quite the same thing as not using a whole feature.

I just know how much work there is to do, at short notice, when a customer comes along offering $$$ for a version of your product on an architecture that you hadn't originally considered. It was definitely worth the hassle of porting and cleaning up to code to provide them with it, but it would have been so much easier if we'd kept it clean from the start.

Re: What I learned from my first C coding challenge

#84

Post by csense » Thu, Sep 06, 2012, 1:25 AM UTC

dbaupp wrote: post #44

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…

(Just as a note, the count-down condition is normally (i = NUMBER; i--; ), the condition you have gives different results: i is 1 larger than one expects.) > Without optimizations turned on, gcc translates both of them to cmpl operations followed by a jne Why would you expect anything different? It isn't doing any optimisations, so it is doing the naive method of transliterating the C to ASM. The actual test is when…

AT&T syntax makes me want to gouge my eyes out.

You have to add these suffixes "l" or "w" to all your instructions to tell the compiler how big they are, but of course if you're using EAX you're talking about a 32-bit register; if you wanted to talk about a 16-bit register, you'd say AX, or AL (or even AH) for 8-bit. An assembler that isn't smart enough to figure out something that simple and obvious is a sorry tool indeed.

And then there's the fact that operands are backwards. "subl $1,eax" translates to "eax -= 1" in C-like syntax. Why switch the order of operands? It's completely unnecessary and confusing. It's like someone inventing a programming language where integer literals were negative if specified with no sign, and only positive if you put a + on them -- technically possible, but the sort of thing that serves no useful purpose and defies all prior conventions, common sense, and sanity.

And putting dollar signs on constants and percent signs on registers? I can't even imagine any possible explanation for that, other than a lazy parser author who didn't care about making extra work for their users. It's the type of corner-cutting that you'd expect to find in some prototype thrown together by a single person in a single evening.

Please, for the sake of your own sanity and those around you, use Intel syntax instead!

Re: What I learned from my first C coding challenge

#85

Post by csense » Thu, Sep 06, 2012, 2:17 AM UTC

icefox wrote: post #62

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…

The best algorithm depends upon the data presented. What is the: - Average number of parameters - The % that are already sorted - The % that don't have keys that start with same letter

It also depends on the assumptions we make about the problem.

- Do we have to validate the URL strings in any way?

- What do we need to do with duplicate names?

- Are cases with small parameter names and/or small numbers of parameters common?

- How common are parameters with lengthy common prefixes?

- Is there a bound on the length of the longest common prefix of two different parameter names?

Tuning or special-casing with common cases in mind can often produce big wins.