Efficiently encoding a hierarchy

Kannan Goundan cakoose@yahoo.com
Sat Jul 14 23:20:00 GMT 2007

(I don't follow this list regularly, but ran into the GIMPLE tuples
proposal and had a suggestion.  Apologies if you were already aware of
this technique.)

The proposed tuple structure has the fields "code" and "subcode".  My
reading of its intent is to allow a simple two-level hierarchy of types.
Another way to encode a hierarchy is to use only a single "code" field
and associate each type with a range of IDs.  For example:

- A (0,5)
  - B (1,1)
  - C (2,4)
    - D (3,3) 
    - E (4,4)
  - F (5,5)
- G (6,7)
  - H (7,7)

A given instance is of type "C" if its "code" field is between 2 and 4,

Advantages of this approach:
- the type hierarchy can be as deep as you like
- checking the exact type is a single comparison
- the subtype check is only two comparisons.
- the ID range is used efficiently (one ID per type)

However, if your hierarchy is really only two levels deep, then the
code/subcode approach has some advantages:
- the subtype check is a single comparison
- you can do a C "switch" on non-leaf types as well

- Kannan

More information about the Gcc mailing list