4 ms·

I don't know why I am wasting my breath either since it is not my law that abstractions (if both implementations are sound) always come with a performance trade

I don't know why I am wasting my breath either since it is not my law that abstractions (if both implementations are sound) always come with a performance tradeoff. It is just a fact (therefore considered a law), not made up by me.

tptacek 14y ago
The opposite is often true. The right abstractions can provide a performance benefit, when they force programs to conform to constructs that are easily expressed in performant native code. The standard C library is full of functions that are slower than equivalent functionality in higher level languages. Or do you think ticking through arrays of hopefully-ASCII bytes, byte by byte, waiting for the 0 byte, is the fastest way to compare two strings?
- haberman 14y ago
  > Or do you think ticking through arrays of hopefully-ASCII bytes, byte by byte, waiting for the 0 byte, is the fastest way to compare two strings? I'm sure you must know this, but this is not even remotely how strcmp() is implemented in modern libc's.
  - aptwebapps 14y ago
    What's a modern libc? Not being snide or anything: I have no idea. I didn't know where to look so I looked at glibc [1] and that, in fact, does seem to be how it works. [1] http://sourceware.org/git/?p=glibc.git;a=blob;f=string/strcmp.c;h=8229d7c773b361a1587cac2cfc5d9b12ba29255a;hb=f1ecb7ef7f5703fc156b8ab2ca153d774c39ec7a http://sourceware.org/git/?p=glibc.git;a=blob;f=string/strcm...
    - pirateking 14y ago
      I have heard of musl[1] and Bionic[2]. Interested in hearing about any others. [1] http://www.musl-libc.org/ http://www.musl-libc.org/ [2] http://en.wikipedia.org/wiki/Bionic_(software) http://en.wikipedia.org/wiki/Bionic_(software)
      - justincormack 14y ago
        Uclibc and dietlibc. Must recommend Musl for code readability and implementation quality.
      - aptwebapps 14y ago
        Those seem to both use basically the same algo as the glibc one, all though a little more compactly written.
    - pbsd 14y ago
      You might want to look at the non-generic implementations, like http://sourceware.org/git/?p=glibc.git;a=blob;f=sysdeps/x86_64/strcmp.S;h=a16d67d37e4787a197a209a1a508c46f4f68e77b;hb=f1ecb7ef7f5703fc156b8ab2ca153d774c39ec7a http://sourceware.org/git/?p=glibc.git;a=blob;f=sysdeps/x86_...
      - aptwebapps 14y ago
        I've never written anything non-trival in C and even that was ages ago so I didn't hope to be able judge the niceties of different implementations but I can't even tell what the algorithm is in that one.
      - darklajid 14y ago
        This might be the most delicious piece of code ever written ( I cannot judge that, really), but we're talking 2307 lines for a string comparison. I'm impressed, but also scared and amused. I always look with envy at system level guys, lacking the knowledge to play on that level. This, though, comforts me quite a bit. That's just not my definition of 'fun'.
  - beagle3 14y ago
    It is quite close, actually. "not even remotely" is a very strong statement. There are tricks that let them do this 8 bytes at a time (on AMD64, 4 bytes on x86), but that doesn't change the fact that in order to compare two 128KB strings which are equal, you actually have to read 2*128KB from memory and compare each single byte (in groups of 8, if you are lucky enough with your alignments and instruction set). Different abstractions, such as Python's strings, can very often do this comparison with almost no memory access: (a) if both strings are interned, it is enough to do a pointer comparison. (b) if the length is not equal, the strings are not equal - a one word comparison. (c) if both strings have been hashed before (quite likely), you can tell they are different if their hash is different - a one word comparison. (d) if length is equal, and hash is (equal or uncomputed), you will have to do the comparison. Whether this trade-off is worthy depends on your application. If most of your strings are 7-characters or less (as is often the case for software dealing with e.g. stock tickers), then the C approach on 64-bit archs wins hands down: you should actually have all the strings in-place because a pointer takes more memory and causes contention. However, if your strings tend to be 100 bytes or above, and many of them have equal prefixes, the Python approach wins hands down.
    - haberman 14y ago
      > There are tricks that let them do this 8 bytes at a time (on AMD64, 4 bytes on x86) It's actually 16 bytes at a time on any machine that supports SSE (maybe 32 bytes soon with AVX). > Different abstractions, such as Python's strings, can very often do this comparison with almost no memory access: Sure, different abstractions have different trade-offs. All of these abstraction possibilities are available to C. strlen() isn't "the C approach," it's just the most common one. Any C application where comparison of long almost-identical strings is important will surely use techniques similar to what Python does. On the other hand, the reverse is not true: Python does not have access to all the same optimizations that a C programmer could draw upon to do string processing.
      - beagle3 14y ago
        I was mostly replying to your assertion that "that's not even remotely how strcmp is implemented", which, for most definition of "even remotely", is false. > All of these abstraction possibilities are available to C That's a tautology at best, and meaningless at worst. The way strcmp() is implemented, which we discussed above, is not actually available in C. > Any C application where comparison of long almost-identical strings is important will surely use techniques similar to what Python does. And similarly, any Python application that requires (insert some uncommon requirement ..) can do what C can with the same kind of help that strcmp() gets - by delegating to the layer that does it best. > Python does not have access to all the same optimizations that a C programmer could draw upon to do string processing. Pure python is more limited than C, true. But specific Python implementations (RPython, PyPy, IronPython) might have better access to some optimizations than specific C implementations. And there's always the aspect of "what's theoretically possible" and "what happens in practice". The fact that PyPy will dynamically switch from 32-bit to 64-bit to unbounded-long-integer might make a real difference on a 32-bit machine where the code might occasionally require 2048 bits, but overwhelmingly requires just 32 bits. It is possible to construct pathological cases where there are e.g. pow(2,128) possible type combinations within a function, the exact combination is only known from the data (but is consistent for an entire run) - in which case, PyPy will essentially compile the right program to machine code, whereas you cannot do AOT because of the number of combinations; which means a C program will essentially be an interpreter based on those types. But I don't care about theoretically constructed pathologies. In practice, especially with time-to-implement constraints, it is not true that a C programmer has all the tools at their disposal that higher level languages have.
- goggles99 14y ago
  Care to provide and example? Your statement would only be true if the abstraction implemented something more efficiently than the C developer. This in of itself says nothing about C or X language for that matter being faster.
  - homeomorphic 14y ago
    It could also be true if the abstraction lays bare optimizations not available (readily enough) to the C compiler. While this wouldn't make X faster than C as languages (what does that mean, anyway?), it could make an X compiler produce faster code than the best C compiler.
    - goggles99 14y ago
      You are not seeing my point. If the JIT compiler can be made better - than so can the C compiler right? Until some point where neither can be made better. Then C would win because it does not carry the extra overhead of the other.
      - homeomorphic 14y ago
        No, not neccessarily. There could be optimization opportunities in the more abstract language that perhaps cannot ever arise in the less abstract.
      - CJefferson 14y ago
        OK, here is an example. Let's consider 'memcpy'. There are various problems with implementing memcpy in C: 1) You can't assume that pointers are aligned. 2) (related) If the user asks for you to copy n bytes, you better not read byte n+1, even if you don't need it, because maybe it is on a different page which is not available for reading. So, an optimised memcpy usually first has to do a bit of work to find the 'aligned segment', do that, topped and tailed with some special cases. A JIT compiler for Javascript (for example) takes issues of alignment out of the hands of the user, so can make any assumptions it wants by keeping such choices away from users. Of course, we could write a memcpy_aligned (and some systems have such a method), but we can't ever optimise simple memcpy as much as the equivalent in javascript.

tptacek 14y ago

The opposite is often true. The right abstractions can provide a performance benefit, when they force programs to conform to constructs that are easily expressed in performant native code. The standard C library is full of functions that are slower than equivalent functionality in higher level languages. Or do you think ticking through arrays of hopefully-ASCII bytes, byte by byte, waiting for the 0 byte, is the fastest way to compare two strings?

haberman 14y ago
> Or do you think ticking through arrays of hopefully-ASCII bytes, byte by byte, waiting for the 0 byte, is the fastest way to compare two strings? I'm sure you must know this, but this is not even remotely how strcmp() is implemented in modern libc's.
- aptwebapps 14y ago
  What's a modern libc? Not being snide or anything: I have no idea. I didn't know where to look so I looked at glibc [1] and that, in fact, does seem to be how it works. [1] http://sourceware.org/git/?p=glibc.git;a=blob;f=string/strcmp.c;h=8229d7c773b361a1587cac2cfc5d9b12ba29255a;hb=f1ecb7ef7f5703fc156b8ab2ca153d774c39ec7a http://sourceware.org/git/?p=glibc.git;a=blob;f=string/strcm...
  - pirateking 14y ago
    I have heard of musl[1] and Bionic[2]. Interested in hearing about any others. [1] http://www.musl-libc.org/ http://www.musl-libc.org/ [2] http://en.wikipedia.org/wiki/Bionic_(software) http://en.wikipedia.org/wiki/Bionic_(software)
    - justincormack 14y ago
      Uclibc and dietlibc. Must recommend Musl for code readability and implementation quality.
    - aptwebapps 14y ago
      Those seem to both use basically the same algo as the glibc one, all though a little more compactly written.
  - pbsd 14y ago
    You might want to look at the non-generic implementations, like http://sourceware.org/git/?p=glibc.git;a=blob;f=sysdeps/x86_64/strcmp.S;h=a16d67d37e4787a197a209a1a508c46f4f68e77b;hb=f1ecb7ef7f5703fc156b8ab2ca153d774c39ec7a http://sourceware.org/git/?p=glibc.git;a=blob;f=sysdeps/x86_...
    - aptwebapps 14y ago
      I've never written anything non-trival in C and even that was ages ago so I didn't hope to be able judge the niceties of different implementations but I can't even tell what the algorithm is in that one.
    - darklajid 14y ago
      This might be the most delicious piece of code ever written ( I cannot judge that, really), but we're talking 2307 lines for a string comparison. I'm impressed, but also scared and amused. I always look with envy at system level guys, lacking the knowledge to play on that level. This, though, comforts me quite a bit. That's just not my definition of 'fun'.
- beagle3 14y ago
  It is quite close, actually. "not even remotely" is a very strong statement. There are tricks that let them do this 8 bytes at a time (on AMD64, 4 bytes on x86), but that doesn't change the fact that in order to compare two 128KB strings which are equal, you actually have to read 2*128KB from memory and compare each single byte (in groups of 8, if you are lucky enough with your alignments and instruction set). Different abstractions, such as Python's strings, can very often do this comparison with almost no memory access: (a) if both strings are interned, it is enough to do a pointer comparison. (b) if the length is not equal, the strings are not equal - a one word comparison. (c) if both strings have been hashed before (quite likely), you can tell they are different if their hash is different - a one word comparison. (d) if length is equal, and hash is (equal or uncomputed), you will have to do the comparison. Whether this trade-off is worthy depends on your application. If most of your strings are 7-characters or less (as is often the case for software dealing with e.g. stock tickers), then the C approach on 64-bit archs wins hands down: you should actually have all the strings in-place because a pointer takes more memory and causes contention. However, if your strings tend to be 100 bytes or above, and many of them have equal prefixes, the Python approach wins hands down.
  - haberman 14y ago
    > There are tricks that let them do this 8 bytes at a time (on AMD64, 4 bytes on x86) It's actually 16 bytes at a time on any machine that supports SSE (maybe 32 bytes soon with AVX). > Different abstractions, such as Python's strings, can very often do this comparison with almost no memory access: Sure, different abstractions have different trade-offs. All of these abstraction possibilities are available to C. strlen() isn't "the C approach," it's just the most common one. Any C application where comparison of long almost-identical strings is important will surely use techniques similar to what Python does. On the other hand, the reverse is not true: Python does not have access to all the same optimizations that a C programmer could draw upon to do string processing.
    - beagle3 14y ago
      I was mostly replying to your assertion that "that's not even remotely how strcmp is implemented", which, for most definition of "even remotely", is false. > All of these abstraction possibilities are available to C That's a tautology at best, and meaningless at worst. The way strcmp() is implemented, which we discussed above, is not actually available in C. > Any C application where comparison of long almost-identical strings is important will surely use techniques similar to what Python does. And similarly, any Python application that requires (insert some uncommon requirement ..) can do what C can with the same kind of help that strcmp() gets - by delegating to the layer that does it best. > Python does not have access to all the same optimizations that a C programmer could draw upon to do string processing. Pure python is more limited than C, true. But specific Python implementations (RPython, PyPy, IronPython) might have better access to some optimizations than specific C implementations. And there's always the aspect of "what's theoretically possible" and "what happens in practice". The fact that PyPy will dynamically switch from 32-bit to 64-bit to unbounded-long-integer might make a real difference on a 32-bit machine where the code might occasionally require 2048 bits, but overwhelmingly requires just 32 bits. It is possible to construct pathological cases where there are e.g. pow(2,128) possible type combinations within a function, the exact combination is only known from the data (but is consistent for an entire run) - in which case, PyPy will essentially compile the right program to machine code, whereas you cannot do AOT because of the number of combinations; which means a C program will essentially be an interpreter based on those types. But I don't care about theoretically constructed pathologies. In practice, especially with time-to-implement constraints, it is not true that a C programmer has all the tools at their disposal that higher level languages have.
goggles99 14y ago
Care to provide and example? Your statement would only be true if the abstraction implemented something more efficiently than the C developer. This in of itself says nothing about C or X language for that matter being faster.
- homeomorphic 14y ago
  It could also be true if the abstraction lays bare optimizations not available (readily enough) to the C compiler. While this wouldn't make X faster than C as languages (what does that mean, anyway?), it could make an X compiler produce faster code than the best C compiler.
  - goggles99 14y ago
    You are not seeing my point. If the JIT compiler can be made better - than so can the C compiler right? Until some point where neither can be made better. Then C would win because it does not carry the extra overhead of the other.
    - homeomorphic 14y ago
      No, not neccessarily. There could be optimization opportunities in the more abstract language that perhaps cannot ever arise in the less abstract.
    - CJefferson 14y ago
      OK, here is an example. Let's consider 'memcpy'. There are various problems with implementing memcpy in C: 1) You can't assume that pointers are aligned. 2) (related) If the user asks for you to copy n bytes, you better not read byte n+1, even if you don't need it, because maybe it is on a different page which is not available for reading. So, an optimised memcpy usually first has to do a bit of work to find the 'aligned segment', do that, topped and tailed with some special cases. A JIT compiler for Javascript (for example) takes issues of alignment out of the hands of the user, so can make any assumptions it wants by keeping such choices away from users. Of course, we could write a memcpy_aligned (and some systems have such a method), but we can't ever optimise simple memcpy as much as the equivalent in javascript.