New "colour" for drawPxel

Libraries, utilities, bootloaders...

Re: New "colour" for drawPxel

Postby Myndale » Sat Sep 13, 2014 9:40 am

rodot wrote:Well why not but how do you flip a single bit in a byte then ?


XOR it with the bit you want to flip:

Code: Select all
if (color == INVERT)
        _displayBuffer[x + (y / 8) * LCDWIDTH_NOROT] ^= _BV(y % 8);


Means you can also flip multiple bits in a byte with the one operation.
Myndale
 
Posts: 507
Joined: Sat Mar 01, 2014 1:25 am

Re: New "colour" for drawPxel

Postby rodot » Sat Sep 13, 2014 10:25 am

I tried your method, it's like 4% faster... seems that the compiler already does a pretty good optimization.
If you manage to implement it for it to be way faster, then I'd be glad to accept your pull request :)
User avatar
rodot
Site Admin
 
Posts: 1290
Joined: Mon Nov 19, 2012 11:54 pm
Location: France

Re: New "colour" for drawPxel

Postby Myndale » Sat Sep 13, 2014 11:31 pm

Yeah, the performance increase of that trick is pretty much eclipsed by the overhead of the division and multiplication in calculating the screen address. Also the penalty of doing a branch is minor on Arduino due to its simplistic 2-stage single-level instruction pipeline. Conditional branching is particularly expensive on architectures with multiple overlapping pipelines because they all have to be stalled while the CPU figures out which branch it needs to take. Good branch prediction helps but the CPU doesn't always get it right, so on those architectures you really need to do everything you can to avoid "if" statements in your performance-critical code sections.
Myndale
 
Posts: 507
Joined: Sat Mar 01, 2014 1:25 am

Re: New "colour" for drawPxel

Postby rodot » Sun Sep 14, 2014 5:46 am

Thanks for this clarification, I'll have to read some documentation about CPU architecture and branch prediction to have a deeper understanding of what you said :roll:
User avatar
rodot
Site Admin
 
Posts: 1290
Joined: Mon Nov 19, 2012 11:54 pm
Location: France

Re: New "colour" for drawPxel

Postby DFX2KX » Sun Sep 14, 2014 3:42 pm

Myndale wrote:Yeah, the performance increase of that trick is pretty much eclipsed by the overhead of the division and multiplication in calculating the screen address. Also the penalty of doing a branch is minor on Arduino due to its simplistic 2-stage single-level instruction pipeline. Conditional branching is particularly expensive on architectures with multiple overlapping pipelines because they all have to be stalled while the CPU figures out which branch it needs to take. Good branch prediction helps but the CPU doesn't always get it right, so on those architectures you really need to do everything you can to avoid "if" statements in your performance-critical code sections.

doesn't that affect pretty much any conditional? If so, that would suck trying to avoid for and while, too.
DFX2KX
 
Posts: 250
Joined: Mon Apr 14, 2014 3:48 am

Re: New "colour" for drawPxel

Postby Myndale » Sun Sep 14, 2014 9:24 pm

DFX2KX wrote:doesn't that affect pretty much any conditional? If so, that would suck trying to avoid for and while, too.


Absolutely! Which is why you use things like unrolled loops to minimize branching and the overhead of loop mechanics etc. In general though it's difficult or impossible to eliminate a for or while loop unless you know in advance how many iterations you need to make, whereas with if statements it's a lot easier. For example a boolean is typically stored as either a 0 or 1, so a statement like this...

Code: Select all
if (my_boolean)
   some_variable = value1;
else
   some_variable = value2;


...can be replaced with a linear interpolation, eliminating the conditional altogether:

Code: Select all
   some_variable = my_boolean*value1 + (1-my_boolean) * value2;


It's much slower on a device like Arduino but it can be used to get huge speed-ups on some other architectures.
Myndale
 
Posts: 507
Joined: Sat Mar 01, 2014 1:25 am

Re: New "colour" for drawPxel

Postby DFX2KX » Sun Sep 14, 2014 10:50 pm

I didn't know you could do a conditional test with just math. Myndale. You're officially the forum computer sage.
DFX2KX
 
Posts: 250
Joined: Mon Apr 14, 2014 3:48 am

Re: New "colour" for drawPxel

Postby TheTurnipKing » Mon Sep 15, 2014 3:19 am

This is a good thread. We have learned a lot.
TheTurnipKing
 
Posts: 13
Joined: Wed Sep 10, 2014 3:29 am

Re: New "colour" for drawPxel

Postby Myndale » Mon Sep 15, 2014 7:14 am

DFX2KX wrote:You're officially the forum computer sage.


Lol, I dunno about that, but thanks anyway :D One of my favourite resources for this kind of thing is the Bit Twiddling Hacks page, has some really clever hacks:

https://graphics.stanford.edu/~seander/bithacks.html
Myndale
 
Posts: 507
Joined: Sat Mar 01, 2014 1:25 am

Previous

Return to Software Development

Who is online

Users browsing this forum: No registered users and 28 guests

cron