указатели на функции в циклах

Question

для моей дипломной работы я написал программу (на C) для сортировки больших таблиц, и теперь все работает как надо.Однако для некоторых моих тестовых файлов программа работает немного медленно.Чтобы иметь возможность более эффективно хранить временные данные, пользователь может указать тип данных для каждого столбца таблицы.Затем входные данные сначала анализируются в некоторый двоичный формат, затем сортируются и, наконец, преобразуются обратно в текстовую форму.

Для каждого типа данных необходимо реализовать четыре функции (кодирование, декодирование, получение и сравнение) и указатели.к ним хранятся в массиве для каждого столбца.Итак, чтобы сделать что-нибудь со строкой таблицы, я должен вызвать правильную функцию для каждой строки в цикле, которая имеет значительные накладные расходы, если столбцы довольно короткие.

Например, здеськод моей функции сравнения строк (вызывается из qsort):

int line_cmp(const void *p1,const void *p2)
{
    int i,o1=0,o2=0,r;

    for(i=0;i<opt.nocols;i++)
        if((r=(*opt.cols[i].cmp)(*(char* const*)p1,&o1,
                                 *(char* const*)p2,&o2)))
            return r;

    return 0;
}

Эта функция циклически проходит по всем столбцам, и если вызываемая функция возвращает значение, отличное от 0 (что означает, что оно не равно), возвращается значение (простокак требует qsort).

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

РЕДАКТИРОВАТЬ: я использую указатели функций, чтобы третье лицо могло разрабатывать произвольные типы данных.Затем они будут загружены (dlopen и т. Д.).Таким образом, я не могу придумать общий двоичный формат для сравнения столбцов, а двоичные данные - просто черный ящик для моей программы.

Answer 1

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

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

Попробуйте сделать что-то вроде

size_t nocols = opt.nocols
columnType const*const myFunc = opt.cols;

и используйте nocols и myFunc[i].comp для цикла.

Answer 2

Я не вижу места для большой оптимизации в функции, которую вы опубликовали. Это просто цикл for, который каждый раз вызывает функцию.

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

Одна из возможных идей состоит в том, чтобы ваша пользовательская функция сравнивала все столбцы. Это может устранить петлю for в опубликованной вами функции. Хотя подобный цикл может потребоваться в специализированной функции, сокращение количества вызовов может сократить время. Однако, если в одной строке может быть несколько типов, это не сработает.

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

Answer 3

Сделайте это параллельным, обновите свой дизайн до параллельной сортировки без блокировки. Возможно, free-free - это скорее проект с мастер-уровнем, если вы не можете придумать Lock-Free, выбирайте блокировку.

Answer 4

Можно ли перейти на C ++?

Я спрашиваю, потому что алгоритм сортировки шаблонов в C ++ STL обычно приводит к встроенному сравнению и хорошему повышению производительности.Разница наиболее заметна при сравнении простых типов, таких как int.

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

Прочитав ваш EDIT, я думаю, что вы не сможете ускорить сортировку без каких-либо радикальных изменений, таких как параллельная сортировка или требование от пользователя предоставить данные в более подходящем формате.

Еще одна идея: Возможно, вы можете ускорить сортировку, последовательно сортируя по столбцам.Это может принести значительную прибыль от местоположения кэша.