Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Imagine that we have some Clang structs with alot of fields and we want to (this is cited from a TODO in a
- linux kernel module):
- "Put the most frequently accessed fields at the beginning of structures to maximize cache efficiency."
- Consider this example program:
- #include <stdio.h>
- #include <stdlib.h>
- struct car {
- char name[16];
- float km_h;
- float fuel_efficiency;
- float price;
- };
- struct car_grading {
- float km_h_multiplier;
- float fuel_efficiency_multiplier;
- float price_multiplier;
- float maximum_price;
- };
- struct car_grading *g;
- static int grading_function(struct car *a)
- {
- return (int) (a->km_h * g->km_h_multiplier +
- a->fuel_efficiency * g->fuel_efficiency_multiplier +
- (a->price - g->maximum_price) * g->price_multiplier);
- }
- int compare_cars(const void *hi, const void *lo)
- {
- struct car *__hi = (struct car *) hi;
- struct car *__lo = (struct car *) lo;
- if(__lo->price > g->maximum_price)
- return 1;
- if(__hi->price > g->maximum_price)
- return -1;
- return (grading_function(__hi) - grading_function(__lo));
- }
- int main(void)
- {
- struct car cars[] = {
- {"Ferrari", 200.f, 30.f, 50000.f},
- {"Opel", 150.f, 20.f, 15000.f},
- {"Citroen", 100.f, 25.f, 11000.f},
- { }
- };
- g = malloc(sizeof(struct car_grading));
- g->km_h_multiplier = 1.f;
- g->fuel_efficiency_multiplier = 3.f;
- g->price_multiplier = 2.f;
- g->maximum_price = 23000.f;
- qsort((void *) cars, 3, sizeof(struct car), compare_cars);
- printf("gonna buy this car: %s\n", cars[2].name);
- return 0;
- }
- The lesson learned from this program: char 'name' [8] is the *first* field in
- struct 'car' but it's used only *once*.
- The fields 'km_h' and 'fuel_efficiency' are used the same amount, but 'price' is used
- *more*, but it's the *last* field!
- It would be better to organise struct 'car' like this:
- struct car {
- float price;
- float km_h;
- float fuel_efficiency;
- char name[16];
- };
- In struct 'car_grading', the field 'maximum_price' should be put at the top, like this:
- struct car_grading {
- float maximum_price;
- float km_h_multiplier;
- float fuel_efficiency_multiplier;
- float price_multiplier;
- };
- It is easy to predict the behaviour of a simple program. Larger programs,
- with more and less frequently used functions, complex control flows, and larger structures, could benefit from counting
- the usage of every field in important and large structures.
- A way to do that would be to "inject" into the program:
- 1. a special table in a new assembly .section, called ".debug_field_frequency",
- 2. code, that updates some counter in that table before some field of some structure is used.
- Obviously, the code will only be "injected" into functions, static to the main compilation unit.
- I used the library qsort() in my program, because it doesn't really do anything with the structure fields, it works on
- structure pointers and throws them to compare_and_maybe_swap_cars().
- The definition of field usage:
- 1. assigning values,
- 2. checking values and using values,
- 3. sending values to another function (that could be under using values).
- Basicly, everything that would do mov %some_register, -location_of_field(%stack_pointer).
- Our parsers algorithm:
- Global vars:
- Let num_structures be 0
- Let field_frequency_table_size be 0
- Initialize circular linked list struct_to_ID
- (this should be in the callback, that's triggered for every struct that has __attribute__ ((field_frequency))
- Print "structure with ID $num_structures is" name_of_structure(this_structure)
- Insert new node with values #name_of_structure, and field_frequency_table_size to struct_to_ID
- Increment num_structures
- Add number_of_fields(this_structure) to field_frequency_table_size
- (this should be in the callback that's triggered in every function)
- For every function
- Check in FnDecl.Args it accepts pointers to atleast one of the tracked structures and store that in bool accepts_pointers
- Check in Fndecl.Body.Decl if it initialises any tracked structures' fields.
- If not And If accepts_pointers is false
- Break
- For every field usage (see our definition of field usage)
- find the appropriate structure in the struct_to_ID linked list
- Let tmp be offsetof(this_structure) (we get that from the node) + offsetof(used_field, this_structure)
- write "asm ("mov -tmp(stack location of field_frequency_table, %eax");"
- "asm ("add %eax, 1");"
- "asm ("mov -tmp(stack location of field_frequency_table, %eax");"
- (also need to write to main.Body.Decl)
- Write ("unsigned long field_frequency_table[field_frequency] __attribute__ ((section ".debug_field_frequency")) = { };")
- What I am asking is: is there a way to do it without using custom attributes, and if now, how to start?
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement