Sign in to follow this  
Finalspace

Cost of Abstraction

Recommended Posts

I found a forum post about someone wanting to easy iterating over a range of numbers -> normal for loops are too heavy, too error prune...

The answer from one guy was very interesting, so i want to share that with you:

 

This is the code he put up there:

namespace util {
    class range {
    public:
        class iterator {
            friend class range;
        public:
            long int operator *() const {
                return i_;
            }
            const iterator &operator ++() {
                ++i_; return *this;
            }
            iterator operator ++(int) {
                iterator copy(*this); ++i_; return copy;
            }

            bool operator ==(const iterator &other) const {
                return i_ == other.i_;
            }
            bool operator !=(const iterator &other) const {
                return i_ != other.i_;
            }

        protected:
            iterator(long int start) : i_(start) {
            }

        private:
            unsigned long i_;

        };

        iterator begin() const {
            return begin_;
        }
        iterator end() const {
            return end_;
        }
        range(long int  begin, long int end) : begin_(begin), end_(end) {
        }
    private:
        iterator begin_;
        iterator end_;

    };
};

So that you can easiely iterate over a range of numbers with a crap api:

auto range = util::range(firstIndex, lastIndex + 1);
    for (auto i : range) {
        std::cout << i << std::endl;
    }

I have no words for this, just compare it with a simple for loop doing the same thing.

Without any compiler optimization, its ridiculous how much instructions you pay for abstraction like this.

 

Crap like this is the reason why almost every software on this planet is slow - especially the web!

This is just a simple for loop, imaging that more complex stuff are build like this...

 

What do you think?

Edited by Finalspace

Share this post


Link to post
Share on other sites

Has been addressed by Stroustrup (mid-2015), most recent wording (2017):

https://github.com/isocpp/CppCoreGuidelines/blob/master/docs/P0122R4.pdf

 

Working implementation:

https://github.com/Microsoft/GSL/blob/master/include/gsl/span

alternatively:

https://github.com/martinmoene/gsl-lite/tree/master/include/gsl

 

Alternative/concurrent approach: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/n4651.pdf

One of the two might hopefully make it into C++20 (I understand C++17 is feature-complete, and span/range is not in).

Edited by samoth

Share this post


Link to post
Share on other sites

This just seems like a way to prevent things that the programmer shouldn't do in the first place, anyway (not modify i_ inside the loop). To me, it's just bad practice to prevent bad practice. Also slower.

 

edit:

I know these things emerge from beginners in their beginning years, trying to abstract things, because they are in the heat. What surprises me is how all this kind of convoluted pattern is passed forward around the internet.

 

KISS

Edited by felipefsdev

Share this post


Link to post
Share on other sites

But if you don't have compiler optimization, you shouldn't use C++ anyway.

It should be noted that neither of these is truly correct. With a not-totally-shit compiler, the cost of abstraction is close to zero in a non-optimized build, and exactly zero in an optimized build.

It's commonly said that you can tell how many C++ features a game uses by the difference in speed in its debug vs optimized build :lol:
C'mon debuggable optimized builds from modern compilers... many game platforms don't support this yet though.

Share this post


Link to post
Share on other sites

Even with O2 activated you still have more cycles you pay for using this abstraction. Sure its much lesser than debug mode - but its still there and thats the thing it bugs me. I double checked that in VStudio 2015.

 

If i really want to abstract that, than i simply make a macro like this:

#define FOR_RANGE_NUMERIC(value, range) for (int value = 0; value < range; ++value)
FOR_RANGE_NUMERIC(index, 100) {
   // index goes from 0 to 99
}

And in the rare case i really really need to have some special thing, i do it like this:

struct forlooprange {
  int start, end;
}
#define FOR_RANGE_STRUCT(value, range) for (int value = (range).start; value <= (range).end; ++value)
FOR_RANGE_STRUCT(index, {0, 100}) {
  // Index goes from 0 to 100
}
Edited by Finalspace

Share this post


Link to post
Share on other sites

I double checked that in VStudio 2015.

Well, try a no-shit compiler then: https://godbolt.org/g/fzUlOH

mov     edi, .L.str
xor     esi, esi
xor     eax, eax
call    printf

I challenge you to write code that is free of those super-heavyweight abstractions and that performs significantly better than this.

Inline assembly allowed if you like... :)

 

(EDIT: I just noticed that I'm only printing out indices (identical to what you're doing) when actually I intended to print values from the array, which is somewhat more meaninful for ranges -- hence the superfluous array. Just ignore that.

Results in basically the same code either way, only a load from memory instead of an immediate load. Same if you use std::array or even  std::vector instead of a C array too, by the way, only a call to operator new and operator delete at the beginning/end of main in the case of using a vector, which is however a kinda obvious necessity if you dynamically allocate something).

Edited by samoth

Share this post


Link to post
Share on other sites

Did you time it? Can you compile both to assembly language and post the difference?

 

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <limits.h>

#define MAX_ITER 100000000
#define TEST_A

#ifdef TEST_A
namespace util {
class range {
public:
class iterator {
friend class range;
public:
unsigned long int operator *() const {
    return i_;
}
const iterator &operator ++() {
    ++i_; return *this;
}
iterator operator ++(int) {
    iterator copy(*this); ++i_; return copy;
}
bool operator ==(const iterator &other) const {
    return i_ == other.i_;
}
bool operator !=(const iterator &other) const {
    return i_ != other.i_;
}
protected:
iterator(unsigned long int start) : i_(start) {
}
private:
unsigned long int i_;
};
iterator begin() const {
return begin_;
}
iterator end() const {
return end_;
}
range(unsigned long int  begin, unsigned long int end) : begin_(begin), end_(end) {
}
private:
iterator begin_;
iterator end_;
};
};

int main(int argc, char **args)
{
    unsigned long int i;
    unsigned long int var = 0;
    struct timespec time_start = {0,0};
    struct timespec time_end = {0,0};
    printf("USING CLASS, %d iterations:\n", MAX_ITER);
    clock_gettime(CLOCK_MONOTONIC, &time_start);
    auto range = util::range(0, MAX_ITER);
    for (auto i : range) {
        var = var + 1;
    }
    clock_gettime(CLOCK_MONOTONIC, &time_end);
    printf("Time: %.5f seconds\n",
        ((double)time_end.tv_sec + 1.0e-9 * time_end.tv_nsec) -
        ((double)time_start.tv_sec + 1.0e-9 * time_start.tv_nsec));
    return 0;
}
#endif

#ifdef TEST_B
int main(int argc, char **args)
{
    unsigned long int i;
    unsigned long int var = 0;
    struct timespec time_start = {0,0};
    struct timespec time_end = {0,0};
    printf("NO CLASS, %d iterations:\n", MAX_ITER);
    clock_gettime(CLOCK_MONOTONIC, &time_start);
    for (i = 0; i < MAX_ITER; i++) {
        var = var + 1;
    }
    clock_gettime(CLOCK_MONOTONIC, &time_end);
    printf("Time: %.5f seconds\n",
        ((double)time_end.tv_sec + 1.0e-9 * time_end.tv_nsec) -
        ((double)time_start.tv_sec + 1.0e-9 * time_start.tv_nsec));
    return 0;
}
#endif

NO CLASS, 100000 iterations:
Time: 0.00094 seconds

NO CLASS, 1000000 iterations:
Time: 0.00809 seconds

NO CLASS, 10000000 iterations:
Time: 0.05149 seconds

NO CLASS, 100000000 iterations:
Time: 0.44766 seconds

 

USING CLASS, 100000 iterations:
Time: 0.00251 seconds

USING CLASS, 1000000 iterations:
Time: 0.01749 seconds

USING CLASS, 10000000 iterations:
Time: 0.13273 seconds

USING CLASS, 100000000 iterations:
Time: 1.35591 seconds

Share this post


Link to post
Share on other sites

I was about to say that any decent compiler would notice that all the loop is doing is twiddling a few locals that never get referenced, so it doesn't have to implement the loop at all.

Share this post


Link to post
Share on other sites

Allow me to translate this code

int main(int argc, char **args)
{
    unsigned long int i;
    unsigned long int var = 0;
    struct timespec time_start = {0,0};
    struct timespec time_end = {0,0};
    printf("USING CLASS, %d iterations:\n", MAX_ITER);
    clock_gettime(CLOCK_MONOTONIC, &time_start);
    auto range = util::range(0, MAX_ITER);
    for (auto i : range) {
        var = var + 1;
    }
    clock_gettime(CLOCK_MONOTONIC, &time_end);
    printf("Time: %.5f seconds\n",
        ((double)time_end.tv_sec + 1.0e-9 * time_end.tv_nsec) -
        ((double)time_start.tv_sec + 1.0e-9 * time_start.tv_nsec));
    return 0;
}

to how an optimizing compiler reads it:

int main()
{
    printf("blah", immediate value);
    time_gettime();
    // what the hell?
    // you think I'll execute invariant code?
    time_gettime();
    printf(time2 - time1);
}

Consequently, the optimizing compiler will transform the above into two consecutive calls to time_gettime followed by printing the difference, which times nothing but the duration of a syscall: https://godbolt.org/g/ACQaqO

Edited by samoth

Share this post


Link to post
Share on other sites

Allow me to translate this code

int main(int argc, char **args)
{
    unsigned long int i;
    unsigned long int var = 0;
    struct timespec time_start = {0,0};
    struct timespec time_end = {0,0};
    printf("USING CLASS, %d iterations:\n", MAX_ITER);
    clock_gettime(CLOCK_MONOTONIC, &time_start);
    auto range = util::range(0, MAX_ITER);
    for (auto i : range) {
        var = var + 1;
    }
    clock_gettime(CLOCK_MONOTONIC, &time_end);
    printf("Time: %.5f seconds\n",
        ((double)time_end.tv_sec + 1.0e-9 * time_end.tv_nsec) -
        ((double)time_start.tv_sec + 1.0e-9 * time_start.tv_nsec));
    return 0;
}

to how an optimizing compiler reads it:

int main()
{
    printf("blah", immediate value);
    time_gettime();
    // what the hell?
    // you think I'll execute invariant code?
    time_gettime();
    printf(time2 - time1);
}

Consequently, the optimizing compiler will transform the above into two consecutive calls to time_gettime followed by printing the difference, which times nothing but the duration of a syscall: https://godbolt.org/g/ACQaqO

 

g++ 4.8.5 optimizes away the whole thing in both cases, so I get "0.00000 seconds".

Perhaps you should use a more realistic setup.

 

In both tests I don't use optimization, which makes both tests run the loop. Compiled on g++ version 6.3.1

Edited by felipefsdev

Share this post


Link to post
Share on other sites

Test_A and Test_B produce the exact same assembly.  I used Compiler Explorer with your code using GCC 6.3 (-std=c++1z -O3) and just changed the define

Test A

.LC0:

        .string "USING CLASS, %d iterations:\n"

.LC2:

        .string "Time: %.5f seconds\n"

main:

        pxor    xmm0, xmm0

        sub     rsp, 40

        mov     esi, 100000000

        mov     edi, OFFSET FLAT:.LC0

        xor     eax, eax

        movaps  XMMWORD PTR [rsp], xmm0

        movaps  XMMWORD PTR [rsp+16], xmm0

        call    printf

        mov     rsi, rsp

        mov     edi, 1

        call    clock_gettime

        lea     rsi, [rsp+16]

        mov     edi, 1

        call    clock_gettime

        pxor    xmm0, xmm0

        mov     edi, OFFSET FLAT:.LC2

        movsd   xmm2, QWORD PTR .LC1[rip]

        mov     eax, 1

        pxor    xmm1, xmm1

        cvtsi2sdq       xmm0, QWORD PTR [rsp+24]

        mulsd   xmm0, xmm2

        cvtsi2sdq       xmm1, QWORD PTR [rsp+16]

        addsd   xmm0, xmm1

        pxor    xmm1, xmm1

        cvtsi2sdq       xmm1, QWORD PTR [rsp+8]

        mulsd   xmm1, xmm2

        pxor    xmm2, xmm2

        cvtsi2sdq       xmm2, QWORD PTR [rsp]

        addsd   xmm1, xmm2

        subsd   xmm0, xmm1

        call    printf

        xor     eax, eax

        add     rsp, 40

        ret

.LC1:

        .long   3894859413

        .long   1041313291

Test B

.LC0:

        .string "NO CLASS, %d iterations:\n"

.LC2:

        .string "Time: %.5f seconds\n"

main:

        pxor    xmm0, xmm0

        sub     rsp, 40

        mov     esi, 100000000

        mov     edi, OFFSET FLAT:.LC0

        xor     eax, eax

        movaps  XMMWORD PTR [rsp], xmm0

        movaps  XMMWORD PTR [rsp+16], xmm0

        call    printf

        mov     rsi, rsp

        mov     edi, 1

        call    clock_gettime

        lea     rsi, [rsp+16]

        mov     edi, 1

        call    clock_gettime

        pxor    xmm0, xmm0

        mov     edi, OFFSET FLAT:.LC2

        movsd   xmm2, QWORD PTR .LC1[rip]

        mov     eax, 1

        pxor    xmm1, xmm1

        cvtsi2sdq       xmm0, QWORD PTR [rsp+24]

        mulsd   xmm0, xmm2

        cvtsi2sdq       xmm1, QWORD PTR [rsp+16]

        addsd   xmm0, xmm1

        pxor    xmm1, xmm1

        cvtsi2sdq       xmm1, QWORD PTR [rsp+8]

        mulsd   xmm1, xmm2

        pxor    xmm2, xmm2

        cvtsi2sdq       xmm2, QWORD PTR [rsp]

        addsd   xmm1, xmm2

        subsd   xmm0, xmm1

        call    printf

        xor     eax, eax

        add     rsp, 40

        ret

.LC1:

        .long   3894859413

        .long   1041313291

The only difference was the string definition.

.string "USING CLASS, %d iterations:\n"          .string "NO CLASS, %d iterations:\n"

Share this post


Link to post
Share on other sites

Just kinda thinking out loud, but it seems to me like if you've worked yourself into some kind of corner where you have to optimize how many instructions get spit out for using for loops, then something else is already wrong.  I can understand that some people are more comfortable working with structures and things that either make life easier, or make code more readable in exchange for some overhead, and I get that a literal for-loop is not always the most appropriate choice, but a lot of these sort of "utility functions" strike me as trying to out-smart the language, or be clever for clever's sake, with not much real world benefit.  Great, you've shaved a few micro seconds from your iteration code - but the real problem might be that you're iterating over too many things in the first place, since we're optimizing loops instead of optimizing the actual content of the game scene or whatever else have you.  ¯\_(?)_/¯

To be fair, I do spend a lot of time in javascript-land where people invent all kinds of "clever" nonsense- trying to recreate features of languages they're more comfortable with, or trying to turn every tiny function of a system into "modules" with all the overhead and process and dependencies etc. that go along with it *cough*node*cough*.

I won't claim to have anything really valuable to say about which approach is reaaaaaally "the best" way to go in this specific case, or which is really faster or more correct, but I'm usually very leary of code that's trying to be "clever" when there was no good reason not to use a straightforward approach in the first place.  Just my 2c.

Edited by TedEH

Share this post


Link to post
Share on other sites

I know these things emerge from beginners in their beginning years, trying to abstract things, because they are in the heat
I believe the real culprit here is not abstraction but over-generalization for future, currently unknown, extensions. It leads to lots of layers through interfaces, derived classes, etc, all because maybe you need to extend in such and such direction tomorrow.

(Things get worse if you try to build a framework or library, like a game engine, as you really don't know where people will extend it.)

Share this post


Link to post
Share on other sites

 

 

C/C++ for-loops are overpowered for most uses

 

What the hell?

 

 

It's a heavily overloaded statement used for a bunch of related but different purposes - creating number sequences, iterating over arrays, iterating using arbitrary iterators, infinite loops, while loops, do-while loops, etc. It contains 3 separate expressions, each of which can (and often is) used in weird ways to get subtly different iterating behaviour, leading to code that is harder to read.

If you want to iterate over a container, a "for element in container" style loop makes more sense. The language should be able to extract the start and end position accordingly. Vectors and arrays can be included in this.

If you have some sort of iterator, then arguably a while loop fits that semantic better. C++ wedges them into the for-statement via the help of hacks like the magical default-constructed input iterator that marks an end of a sequence. It's not a natural fit.

If you want to create a number sequence, that can be a separate operation. e.g. a Range() function. Then, iterating over it is optional - which is good, because that's often suboptimal anyway, in these days of vectorisation and parallelism you don't really want explicit loops everywhere.

If you want an infinite loop then that's what 'while' is there for - not "for (;;)". Same goes for any other loop that would be a [do]-while in other languages - those constructs exist because they're clearer, semantically.

 

 

What is the correlation, in this case, between versatility/utility and being over-powered?

TBH I think I understand what you may have had in mind with your original statement. It's just that I find the wording fantastically misleading and your explanation actually further deviates from what I thought you meant. If anything, your elaboration works directly against it, hilighting how a for-loop is too specific/ill-suited for most cases, making it, effectively, underpowered. I personally find it simple and slick, and prefer it whenever possible.

Just to express what I had in mind with my reply: a for-loop is a flow control construct. It has nothing to do with power. Whether it is well or poorly suited for a task stems from the choice made by the programmer, not the construct itself. Misusing flow control is a different topic.

PS: while(1) { } generates a C4127 in VS, which needs to either be explicitly suppressed or replaced with a for(;;) { }.

That being said I digress - this discussion is only remotely related to the topic at hand.

Share this post


Link to post
Share on other sites

Power = "the ability or capacity to do something". The for-statement in C, C++, etc., has the ability and capacity to do too many different things. That's overpowered.

Abominations like this, for example:

for (char *p = strtok(s," "); p != NULL; p = strtok(NULL, " "))
{
    puts(p);
}

Obviously you want your language to be powerful, but it doesn't follow that each statement in it needs to be.

Reducing it down to "a choice by the programmer" ignores the fact that the language shapes the code and the thought processes.

And MS docs disagree with you, saying "trivial constants such as 1 or true do not trigger the warning". (Besides which, I'm much happier to say that a warning is erroneous than to think that 'for ( ; ; )' is a sensible construct.)

Share this post


Link to post
Share on other sites

If you have some sort of iterator, then arguably a while loop fits that semantic better. C++ wedges them into the for-statement via the help of hacks like the magical default-constructed input iterator that marks an end of a sequence. It's not a natural fit.


I wouldn't call it a hack. I believe the reason C++ does this is that it's the most natural way to iterate through an array. For continguous data structures like arrays, you can get away with using a simple pointer as your iterator - in fact, I've worked with production code that does just this, including using pointers with the standard algorithms! I imagine vectors are among the most common STL data structures used in C++, so it makes sense to me that dominant iterator pattern would match the most natural way to iterate through them.

Pointer-style iterators fit well into C++'s mindset of "don't pay for what you don't use." You could abstract the whole thing with a Java-style iterator, but it would have to store both a pointer to the current element and a pointer to the last/one past element, bloating the size of the iterator. Probably not a problem on modern hardware - very slightly increased chance of cache misses on the stack aside - but what about on embedded systems? Everyone would just use the pointer-style iterators, anyway.

edit: Though, if you wanted to get rid of the extra pointer I suppose you could do something like this:
 
for (auto itor = std::begin(container); itor.is_valid_in(container); ++itor)
But then
1) You can't make itor a raw pointer and that cuts down on the usefulness of the standard algorithms;
2) That doesn't actually match the Java-style idiom. Edited by Oberon_Command

Share this post


Link to post
Share on other sites

Power = "the ability or capacity to do something". The for-statement in C, C++, etc., has the ability and capacity to do too many different things. That's overpowered.

Abominations like this, for example:

for (char *p = strtok(s," "); p != NULL; p = strtok(NULL, " "))
{
    puts(p);
}

Obviously you want your language to be powerful, but it doesn't follow that each statement in it needs to be.

Reducing it down to "a choice by the programmer" ignores the fact that the language shapes the code and the thought processes.

And MS docs disagree with you, saying "trivial constants such as 1 or true do not trigger the warning". (Besides which, I'm much happier to say that a warning is erroneous than to think that 'for ( ; ; )' is a sensible construct.)

 

Perhaps it would be prudent to add a related footnote to your original post? If nothing else, your original statement is ambiguous - within the confines of the thread at hand I automatically related your use of the word power to execution speed. I still don't agree with you in terms of the versatility of the for-loop (IMO the misuse of anything is ultimately almost always the programmer's failing and the language should not coerce one to learn a crapton of syntax that can be easily generalized). But that's my opinion and a whole different matter.

As for the warning - it may have been fixed post-2013. Honestly I didn't check. In VS2013 the "official" solution is to use for(;;). Which, I agree, is silly at best.

Share this post


Link to post
Share on other sites
Just kinda thinking out loud, but it seems to me like if you've worked yourself into some kind of corner where you have to optimize how many instructions get spit out for using for loops, then something else is already wrong

That really depends. For example, if you are checking for collisions of your object's body in a determined space (whether getting only the neighbors or not), you will use at least one loop. And if you have many objects that perform that operation, things take time. Same goes to "find object that has XYZ state".

 

I know these things emerge from beginners in their beginning years, trying to abstract things, because they are in the heat
I believe the real culprit here is not abstraction but over-generalization for future, currently unknown, extensions. It leads to lots of layers through interfaces, derived classes, etc, all because maybe you need to extend in such and such direction tomorrow.

(Things get worse if you try to build a framework or library, like a game engine, as you really don't know where people will extend it.)

I agree.

But be aware that they do make other programmer's lives easier and they have no runtime cost, so other programmers are going to use them whenever they make sense.

I get, abstraction is to make programmers' life easier, but to go to the point that you need to abstract a for loop? Look that it's the person that @Finalspace mentioned (in the first post) that said "normal for loops are too heavy" and teached that using a class abstraction (written in 40+ lines) in for loops is a magic bullet.

Edited by felipefsdev

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this