NO

Author Topic: #pragma density(0.0)  (Read 3132 times)

Grincheux

  • Guest
#pragma density(0.0)
« on: June 15, 2017, 06:38:59 PM »
I have not really understood the documentation about this pragma.
By default it is 0.5.
How to use it (0.0 ... 1.0)
What is the result on the optimization?
thx

Offline frankie

  • Global Moderator
  • Member
  • *****
  • Posts: 2096
Re: #pragma density(0.0)
« Reply #1 on: June 16, 2017, 12:50:29 PM »
Compilers use a mix of jump tables and binary searches to execute the correct case code in a switch instruction.
I.e.
Code: [Select]
switch a
{
  case 0:
    ...
    break;
  case 1:
    ...
    break;
  case 2:
    ...
    break;
  case 5:
    ...
    break;
  case 6:
    ...
    break;
  case 9:
    ...
    break;
  case 10:
    ...
    break;
}
The code generated will use a binary search to approach the three sequences available: 0-2, 5-6, 9-10. Then will use a (pseudo)jump table to access in the range. I said pseudo jump table because it is not really a table, but a sequence of offsetting addresses and then jump that emulates a jump table mechanism. The problem is that actual CPU's that make intense use of instruction flow caching must reset the caches when jumping. For this reason happens that a binary search, with predictable jumps, works faster than a pure jump table.
When you have very large ranges, i.e. cases 0-999, instead of creating a very large jump table you can decide to reduce it to a fraction and reach inside cases using a binary search.
I.e. crate a table of 10 entries: 0-99, 100-199, 200-299, ..., 900-999.
Then search the subrange using a binary search and last access with a reduced jump table. In this case we used a density  of 0.1.
Also the reverse is possible, using binary search first and table jump after.

Result on optimization is on the quantity of used memory and/or execution speed (memory for tables, speed for binary search code).
Anyway using optimization reset the density to the default that is 0.5.

For a more indeep explanation you can read article from Vlad Lazarenko.
« Last Edit: June 16, 2017, 03:16:26 PM by frankie »
It is better to be hated for what you are than to be loved for what you are not. - Andre Gide

Offline jj2007

  • Member
  • *
  • Posts: 536
Re: #pragma density(0.0)
« Reply #2 on: June 16, 2017, 01:39:32 PM »