Каковы штрафы универсальных функций по сравнению с массивами указателей на функции в C? - PullRequest
Новая
       36

Каковы штрафы универсальных функций по сравнению с массивами указателей на функции в C?

2 голосов
/ 15 февраля 2012

Я пишу матричную библиотеку (часть SciRuby) с несколькими типами хранения («стили») и несколькими типами данных («dtypes»). Например, матрица stype в настоящее время может быть плотной, йельской (AKA 'csr') или списком списков; и dtype может быть int8, int16, int32, int64, float32, float64, complex64 и т. д.

Очень просто написать шаблонный процессор на Ruby или sed, который принимает базовую функцию (например, умножение разреженных матриц) и создает собственную версию для каждого возможного dtype. Я мог бы даже написать такой шаблон для обработки двух разных типов, скажем, если бы мы хотели умножить int32 на float64.

То же самое можно сделать в некоторых случаях для разных стилей. В конечном счете, однако, вы можете получить очень большой набор функций, многие из которых даже не используются в процессе использования большинством людей.

Также легко использовать массивы указателей на функции для обеспечения доступа к этим функциям - и представить даже массив трехмерных указателей на функции не так уж сложно: 

MultFuncs[lhs->stype][lhs->dtype][rhs->dtype](lhs->shape[0], rhs->shape[1], lhs->data, rhs->data, result->data);
// This might point to some function like this:
// i32_f64_dense_mult(size_t, size_t, int32_t*, float64*, float64*);

Конечно, крайняя альтернатива массивам указателей на функции, которые были бы невероятно сложными для кодирования и обслуживания, - это иерархические операторы switch или if / else: 

switch(lhs->stype) {
case STYPE_SPARSE:
  switch(lhs->dtype) {
  case DTYPE_INT32:
    switch(rhs->dtype) {
    case DTYPE_FLOAT64:
      i32_f64_mult(lhs->shape[0], rhs->shape[1], lhs->ija, rhs->ija, lhs->a, rhs->a, result->data);
      break;
    // ... and so on ...

Также кажется, что это будет O ( sd 2 ), где s = количество стилей, d = число dtypes для каждой операции, тогда как массив указателей на функции будет иметь значение O ( r ), где r = число измерений в массиве.

Но есть и третий вариант.

Третий вариант - использовать массивы указателей функций для общих операций (например, копирование из одного неизвестного типа в другой): 

SetFuncs[lhs->dtype][rhs->dtype](5, // copy five consecutive items
 &to, // destination
 dtype_sizeof[lhs->dtype], // dtype_sizeof is a const size_t array giving sizeof(int8_t), sizeof(int16_t), etc.
 &from, // source
 dtype_sizeof[rhs->dtype]);

И затем вызвать это из универсальной функции умножения разреженной матрицы, которая может быть объявлена ​​следующим образом: 

void generic_sparse_multiply(size_t* ija, size_t* ijb, void* a, void* b, int dtype_a, int dtype_b);

И это будет использовать SetFuncs[dtype_a][dtype_b] для ссылки на правильную функцию присваивания, например. Недостатком является то, что вам, возможно, придется реализовать целую кучу из них - IncrementFuncs, DecrementFuncs, MultFuncs, AddFuncs, SubFuncs и т. Д. - потому что вы никогда не будете знать, какие типы ожидать.

Итак, наконец, мои вопросы:

  1. Какова стоимость, если таковая имеется, наличия огромных многомерных константных массивов указателей функций? Большая библиотека или исполняемый файл? Медленное время загрузки? и т.д.
  2. Представляет ли использование обобщений, таких как IncrementFuncs, SetFuncs и т. Д. (Которые, вероятно, зависят от memcpy или типов), барьеры для оптимизации во время компиляции?
  3. Если использовать операторы switch, как описано выше, будут ли они оптимизированы современными компиляторами? Или они будут оцениваться каждый раз?

Я понимаю, что это невероятно сложный набор вопросов.

Если вы можете просто отослать меня к хорошему ресурсу и предпочесть не отвечать напрямую, это прекрасно. Я много использовал Google, прежде чем опубликовать это, но не был уверен, какие поисковые термины использовать.

1 Ответ

4 голосов
/ 15 февраля 2012

Прежде всего, постарайтесь уменьшить сложность функции (ей). Вы должны иметь возможность иметь объявление вроде 

Result_t function (Param_t*);

где Param_t - это структура, содержащая все те вещи, которые вы передаете. Чтобы использовать универсальные типы, включите в структуру enum, сообщающий, какой тип используется, и void * для этого типа.

1. Какова стоимость, если таковая имеется, огромных многомерных константных массивов указателей функций? Большая библиотека или исполняемый файл? Медленный время загрузки? и т.д.

Определенно больший исполняемый файл. Время загрузки зависит от того, для какой системы предназначен код. Если это для системы на основе ОЗУ (ПК и т. Д.), То время загрузки может увеличиться, но это не должно оказывать существенного влияния на производительность. Хотя, конечно, это зависит от того, насколько велик "огромный":)

2.Использует ли обобщения, такие как IncrementFuncs, SetFuncs и т. Д. (Которые, вероятно, зависят от memcpy или typecasts), препятствующие оптимизация во время компиляции?

Наверное, нет, компилятор может оптимизировать так много всего. При работе с общими типами данных в C он часто сводится к memcpy () в конце, который, как мы надеемся, сам по себе реализован так быстро, как копирование.

3.Если бы вы использовали операторы switch, как описано выше, будут ли они оптимизированы современными компиляторами? Или они будут оценены каждый раз?

По иронии судьбы, компилятор, вероятно, оптимизировал бы его в нечто вроде массива указателей на функции. Однако компилятор, вероятно, не может предсказать характер данных, особенно если они заданы во время выполнения.

...