Как я могу реорганизовать этот код с учетом производительности?

Question

У меня есть метод, в котором производительность действительно важна (я знаю, что преждевременная оптимизация - это корень всего зла. Я знаю, что должен, и я сделал профиль моего кода. В этом приложении каждая десятая секунды, которую я сохраняю, является большой победой.) Этот метод использует различные эвристики для генерации и возврата элементов. Эвристика используется последовательно: первая эвристика используется до тех пор, пока она больше не сможет возвращать элементы, затем используется вторая эвристика, пока она больше не сможет возвращать элементы и т. Д. До тех пор, пока не будут использованы все эвристики. При каждом вызове метода я использую переключатель для перехода к правильной эвристике. Это уродливо, но хорошо работает. Вот некоторые псевдо-код

class MyClass 
{ 
private: 
    unsigned int m_step; 
public: 
    MyClass() : m_step(0) {}; 

    Elem GetElem() 
    { 
     // This switch statement will be optimized as a jump table by the compiler. 
     // Note that there is no break statments between the cases. 
     switch (m_step) 
     { 
     case 0: 
     if (UseHeuristic1()) 
     { 
      m_step = 1; // Heuristic one is special it will never provide more than one element. 
      return theElem; 
     } 

     m_step = 1; 

     case 1: 
     DoSomeOneTimeInitialisationForHeuristic2(); 
     m_step = 2; 

     case 2: 
     if (UseHeuristic2()) 
     { 
      return theElem; 
     } 

     m_step = 3; 

     case 3: 
     if (UseHeuristic3()) 
     { 
      return theElem; 
     } 
     m_step = 4; // But the method should not be called again 
     } 

     return someErrorCode; 
    }; 
} 

Как я уже сказал, это работает, и это эффективно, так как при каждом вызове, выполнение прыжков прямо там, где оно должно быть. Если эвристика не может обеспечить элемент, m_step увеличивается (так что в следующий раз мы не будем повторять эту эвристику снова), и потому что нет инструкции break, следующая эвристика проверяется. Также обратите внимание, что некоторые шаги (например, шаг 1) никогда не возвращают элемент, но являются однократной инициализацией для следующей эвристики.

Инициативы причины не все сделано заранее, так как они никогда не понадобятся. Всегда возможно (и часто) для GetElem не получать вызов снова после того, как он возвратил элемент, даже если есть все еще элементы, которые он мог бы вернуть.

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

Как я должен реорганизовать этот код, чтобы он был более читабельным и элегантным, сохраняя его максимально эффективным?

Answer 1

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

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

Answer 2

Оберните каждую эвристику в итераторе. Инициализируйте его полностью при первом вызове hasNext(). Затем собрать все итераторы в списке и использовать супер-итератор для перебора всех из них:

boolean hasNext() { 
    if (list.isEmpty()) return false; 

    if (list.get(0).hasNext()) return true; 

    while (!list.isEmpty()) { 
     list.remove (0); 
     if (list.get(0).hasNext()) return true; 
    } 
    return false; 
} 
Object next() { 
    return list.get (0).next(); 
} 

Примечание: В этом случае, связанный список может быть чуть-чуть быстрее, чем ArrayList, но вы все равно должны проверить это.

[EDIT] Изменено «превратить каждый» в «обертывание каждого», чтобы мои намерения были более ясными.

Answer 3

Похоже, что в этом коде действительно не так много оптимизма - возможно, большая часть оптимизации может быть выполнена в функциях UseHeuristic. Что в них?

Answer 4

Вы можете повернуть поток управления наизнанку.

template <class Callback> // a callback that returns true when it's done 
void Walk(Callback fn) 
{ 
    if (UseHeuristic1()) { 
     if (fn(theElem)) 
      return; 
    } 
    DoSomeOneTimeInitialisationForHeuristic2(); 
    while (UseHeuristic2()) { 
     if (fn(theElem)) 
      return; 
    } 
    while (UseHeuristic3()) { 
     if (fn(theElem)) 
      return; 
    } 
} 

Это может заработать вам несколько наносекунд, если switch отправки и return заявления метания процессора от его походки, и получатель inlineable.

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

Answer 5

Это микро оптимизация, но нет необходимости устанавливать значение m_elem, когда вы не возвращаетесь из GetElem. См. Код ниже.

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

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

class MyClass 
{ 
private: 
    unsigned int m_step; 
public: 
    MyClass() : m_step(0) {}; 

    Elem GetElem() 
    { 
     // This switch statement will be optimized as a jump table by the compiler. 
     // Note that there is no break statments between the cases. 
     switch (m_step) 
     { 
     case 0: 
     if (UseHeuristic1()) 
     { 
      m_step = 1; // Heuristic one is special it will never provide more than one element. 
      return theElem; 
     } 

     case 1: 
     DoSomeOneTimeInitialisationForHeuristic2(); 
     m_step = 2; 

     case 2: 
     if (UseHeuristic2()) 
     { 
      return theElem; 
     } 

     case 3: 
     m_step = 4; 

     case 4: 
     if (UseHeuristic3()) 
     { 
      return theElem; 
     } 
     m_step = 5; // But the method should not be called again 
     } 

     return someErrorCode; 
    }; 
} 

Answer 6

Что вы действительно можете здесь сделать, это заменить условный шаблон состояния.

http://en.wikipedia.org/wiki/State_pattern

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

Что может улучшить производительность, является устранение DoSomeOneTimeInitialisationForHeuristic2(); с отдельным состоянием между. 1 и 2.

Answer 7

Если это не сломано, не исправляйте это.

Это выглядит довольно эффективно, как есть. Не трудно даже понять. Добавление итераторов и т. Д., Вероятно, затруднит понимание.

Вы, вероятно, лучше делать

1. Анализ эффективности. Действительно ли время действительно проведено в этой процедуре или это большая часть функций, которые она вызывает? Я не вижу сколько-нибудь значительного времени здесь.
2. Дополнительные тесты модулей, чтобы кто-то не нарушил его, если им нужно его модифицировать.
3. Дополнительные комментарии в коде.

Answer 8

Я не думаю, что ваш код настолько плохо, но если вы делаете такого рода вещи много, и вы хотите, чтобы скрыть механизмы, так что логика яснее, вы можете посмотреть на Simon Tatham's coroutine macros. Они предназначены для C (используя статические переменные), а не C++ (с использованием переменных-членов), но это тривиально изменить.

Результат должен выглядеть примерно так:

Elem GetElem() 
{ 
    crBegin; 

    if (UseHeuristic1()) 
    { 
    crReturn(theElem); 
    } 

    DoSomeOneTimeInitialisationForHeuristic2(); 

    while (UseHeuristic2()) 
    { 
    crReturn(theElem); 
    } 

    while (UseHeuristic3()) 
    { 
    crReturn(theElem); 
    } 

    crFinish; 
    return someErrorCode; 
} 

Answer 9

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

class MyClass 
{ 
private: 
    typedef bool heuristic_function(); 
    typedef heuristic_function * heuristic_function_ptr; 
    static heuristic_function_ptr heuristic_table[4]; 
    unsigned int m_step; 
public: 
    MyClass() : m_step(0) {}; 

    Elem GetElem() 
    { 
     while (m_step < sizeof(heuristic_table)/sizeof(heuristic_table[0])) 
     { 
     if (heuristic_table[m_step]()) 
     { 
      return theElem; 
     } 
     ++m_step; 
     } 

     return someErrorCode; 
    }; 
}; 

MyClass::heuristic_function_ptr MyClass::heuristic_table[4] = { UseHeuristic1, DoSomeOneTimeInitialisationForHeuristic2, UseHeuristic2, UseHeuristic3 }; 

Answer 10

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

Вызов функции обработки элементов выполняется быстро.

Здесь работает пример кода:

#include <cstdlib> 
#include <iostream> 
using namespace std; 

typedef void (*ElementHandlerFn)(void); 

void ProcessElement0() 
{ 
    cout << "Element 0" << endl; 
} 

void ProcessElement1() 
{ 
    cout << "Element 1" << endl; 
} 
void ProcessElement2() 
{ 
    cout << "Element 2" << endl; 
} 

void ProcessElement3() 
{ 
    cout << "Element 3" << endl; 
} 

void ProcessElement7() 
{ 
    cout << "Element 7" << endl; 
} 

void ProcessUnhandledElement() 
{ 
    cout << "> Unhandled Element <" << endl; 
} 




int main() 
{ 
    // construct a table of function pointers, one for each possible element (even unhandled elements) 
    // note: i am assuming that there are 10 possible elements -- 0, 1, 2 ... 9 -- 
    // and that 5 of them (0, 1, 2, 3, 7) are 'handled'. 

    static const size_t MaxElement = 9; 
    ElementHandlerFn handlers[] = 
    { 
     ProcessElement0, 
     ProcessElement1, 
     ProcessElement2, 
     ProcessElement3, 
     ProcessUnhandledElement, 
     ProcessUnhandledElement, 
     ProcessUnhandledElement, 
     ProcessElement7, 
     ProcessUnhandledElement, 
     ProcessUnhandledElement 
    }; 

    // mock up some elements to simulate input, including 'invalid' elements like 12 
    int testElements [] = {0, 1, 2, 3, 7, 4, 9, 12, 3, 3, 2, 7, 8 }; 
    size_t numTestElements = sizeof(testElements)/sizeof(testElements[0]); 

    // process each test element 
    for(size_t ix = 0; ix < numTestElements; ++ix) 
    { 
     // for some robustness... 
     if(testElements[ix] > MaxElement) 
      cout << "Invalid Input!" << endl; 
     // otherwise process normally 
     else 
      handlers[testElements[ix]](); 

    } 

    return 0; 
}