NO

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

Offline Grincheux

  • Member
  • *
  • Posts: 184
  • Never be pleased, Always Improved
    • Today, it's yestirday and Tomorrow
#pragma density(0.0)
« on: June 15, 2017, 05: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
-------------------
Today, it's yestirday and Tomorrow
Kenavo

Offline frankie

  • Global Moderator
  • Member
  • *****
  • Posts: 1578
Re: #pragma density(0.0)
« Reply #1 on: June 16, 2017, 11:50:29 AM »
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, 02:16:26 PM by frankie »

Offline jj2007

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