Re[6]: Когда linear search быстрее hash map
От: · Великобритания  
Дата: 17.10.17 07:32
Оценка:
Здравствуйте, MTD, Вы писали:

MTD>·>Какая-то фигня.
MTD>Да, так обычно получается, если не прочитать, но начать отвечать.
Я наверное просто к словам придираюсь. " асимптотика поиска одинакова — логарифм" — это верно для абстактной структуры "дерево", "массив". А имплементация даёт изменение асимтотики — индирекция, промах в кеш это по сути дополнительный lookup для процессора, который начинает использовать ассоциативный контейнер страниц памяти для их подгрузки в свой кеш. Т.е. на уровне языка программирования вроде как одно и то же, но если смотреть все слои всего вычислительного устройства — то уже фигня получается. То же и с предсказанием ветвления — это ведь тоже по сути алгоритм со своей сложностью — не всегда его влияние можно отбрасывать.
Т.е. проблема не в асимтотике, а в том как её считают — не учитывают "незначительные" детали.
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re[6]: Когда linear search быстрее hash map
От: Vain Россия google.ru
Дата: 17.10.17 07:42
Оценка:
Здравствуйте, MTD, Вы писали:

MTD>Шапочка из фольги спасет от голосов в голове и вернет душевное здоровье.
Шапочка из фольги на самом деле отражает внутренние голоса обратно в голову. Из-за чего процесс зацикливается и из него нету выхода. Перегрев одним словом наступит.
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Re[4]: Когда linear search быстрее hash map
От: Engler Беларусь  
Дата: 17.10.17 07:58
Оценка: 2 (1)
Здравствуйте, c-smile, Вы писали:

CS>Здравствуйте, Engler, Вы писали:

E>>Здравствуйте, Engler, Вы писали:

E>>В итоге мы имеем хорошо оптимизированную функцию if_t2e,

CS>Что там оптимизировано-то?
Например gcc, вначале сравнивает строки одинаковой длинны (4 байта), потом более длинной, и.т.д
Это если я правильно понял, конечно.
( update: причем компилятор разварачивает сравнение вот таким вот образом

if (str[0] != 't') goto ...
if (str[1] != 'e') goto ...
if (str[2] != 'x') goto ...
if (str[3] != 't') goto ...


И так для всех строк

)

CS>Банальный же if-elif-elif-else... т.е. последовательный (линейный) перебор.
Банальность, это ключ

gcc.godbolt

Я немного добавил тестов, что бы точнее понять, что присходит.
Я добавил 2 вектора [вооще 4, с разным порядком строк, отсортированным по длине, и оригинальным]
std::vector<pair< string, FormatterType> > и
std::vector<pair< aux::chars, FormatterType> > и
Еще в клоне if_t2e немного нагадил компилятору с помощью volatile, потому что могу
и что бы он не харкодил значения, а "честно" читал их как в случае c std::vector



  Код 
#include <iostream>

#include <string>
#include <vector>
#include <chrono>
#include <algorithm>
#include <unordered_map>
#include <string.h>
#include <cassert>

//elements in array literal
#define ITEMS_IN(a) (sizeof(a)/sizeof(a[0]))
//chars in sting literal
#define CHARS_IN(s) (sizeof(s) / sizeof(s[0]) - 1)

namespace aux
{

    template <typename T >
    struct slice
    {
        const T*       start;
        unsigned int   length;

        slice() : start(0), length(0) {}
        slice(const T* start_, size_t length_) { start = start_; length = (unsigned int)length_; }
        slice(const slice& src) : start(src.start), length(src.length) {}
        slice(const std::basic_string<T>& src) : start(src.c_str()), length((unsigned int)src.length()) {}

        slice& operator = (const slice& src) { start = src.start; length = src.length; return *this; }

        const T*      end() const { return start + length; }

        bool operator == (const slice& r) const
        {
            if (length != r.length)
                return false;
            for (unsigned int i = 0; i < length; ++i)
                if (start[i] != r.start[i])
                    return false;
            return true;
        }

        bool operator == (volatile const slice& r) const
        {
            if (length != r.length)
                return false;
            for (unsigned int i = 0; i < length; ++i)
                if (start[i] != r.start[i])
                    return false;
            return true;
        }

        bool operator != (const slice& r) const { return !operator==(r); }

        T operator[] (unsigned int idx) const
        {
            assert(idx < length);
            if (idx < length)
                return start[idx];
            return 0;
        }

        T last() const
        {
            if (length)
                return start[length - 1];
            return 0;
        }

        // [idx1..length)
        slice operator() (unsigned int idx1) const
        {
            assert(idx1 < length);
            if (idx1 < length)
                return slice(start + idx1, length - idx1);
            return slice();
        }
        // [idx1..idx2)
        slice operator() (unsigned int idx1, unsigned int idx2) const
        {
            assert(idx1 < length);
            assert(idx2 <= length);
            assert(idx1 <= idx2);
            if (idx1 < idx2)
                return slice(start + idx1, idx2 - idx1);
            return slice();
        }

        int index_of(T e) const
        {
            for (unsigned int i = 0; i < length; ++i) if (start[i] == e) return i;
            return -1;
        }

        int last_index_of(T e) const
        {
            for (unsigned int i = length; i > 0;) if (start[--i] == e) return i;
            return -1;
        }

        int index_of(const slice& s) const
        {
            if (s.length > length) return -1;
            if (s.length == 0) return -1;
            unsigned int l = length - s.length;
            for (unsigned int i = 0; i < l; ++i)
                if (start[i] == *s.start)
                {
                    const T* p = s.start;
                    unsigned int last = i + s.length;
                    for (unsigned int j = i + 1; j < last; ++j)
                        if (*(++p) != start[j])
                            goto next_i;
                    return i;
                next_i: continue;
                }
            return -1;
        }

        int last_index_of(const slice& s) const
        {
            if (s.length > length) return -1;
            if (s.length == 0) return -1;
            const T* ps = s.end() - 1;
            for (unsigned int i = length; i > 0; )
                if (start[--i] == *ps)
                {
                    const T* p = ps;
                    unsigned int j, first = i - s.length + 1;
                    for (j = i; j > first; )
                        if (*(--p) != start[--j])
                            goto next_i;
                    return j;
                next_i: continue;
                }
            return -1;
        }

        void prune(unsigned int from_start, unsigned int from_end = 0)
        {
            unsigned int s = from_start >= length ? length : from_start;
            unsigned int e = length - (from_end >= length ? length : from_end);
            start += s;
            if (s < e) length = e - s;
            else length = 0;
        }


    };

    typedef slice<char>          chars;
    typedef slice<wchar_t>       wchars;
    typedef slice<unsigned char> bytes;

    // Note: CS here is a string literal!
#define CHARS(CS) aux::slice<char>(CS,CHARS_IN(CS))
#define WCHARS(CS) aux::slice<wchar_t>(WSTR(CS),CHARS_IN(_WSTR(CS)))

    inline wchars  chars_of(const wchar_t *t) { return t ? wchars(t, (unsigned int)wcslen(t)) : wchars(); }
    inline chars   chars_of(const char *t) { return t ? chars(t, (unsigned int)strlen(t)) : chars(); }


    template<typename T>
    slice<T> chars_of(const std::basic_string<T> &s) { return slice<T>(s.c_str(), s.length()); }

    template<typename T>
    slice<T> elements_of(const std::vector<T> &s) { return slice<T>(s.cbegin(), s.size()); }

    template<typename T, int size>
    slice<T> elements_of(T(&arr)[size]) { return slice<T>(&arr[0], size); }

    template<typename T, int size>
    slice<T> elements_of(const T(&arr)[size]) { return slice<T>(&arr[0], size); }

    template<typename T>
    std::basic_string<T> make_string(aux::slice<T> s) { return std::basic_string<T>(s.start, s.length); }

}

enum FormatterType {
    simple_formatter,
    integer_formatter,
    decimal_formatter,
    currency_formatter,
    date_formatter,
    date_local_formatter,
    time_formatter,
    time_local_formatter,
    enum_formatter,
    duration_formatter
};

enum { TOTAL_RUNS = 10000 };

std::string input_tokens[] = { "", "text", "integer", "decimal", "currency", "date", "date-local", "time", "time-local", "enum" };

std::vector<std::string> input;

void generate_input() {
    for (int n = 0; n < TOTAL_RUNS; ++n)
        input.push_back(std::string(input_tokens[std::rand() % ITEMS_IN(input_tokens)]));
}

FormatterType if_t2e(const std::string& name)
{
    aux::chars name_chars = aux::chars_of(name);
    auto result =
        name_chars == CHARS("text") ? simple_formatter
        : name_chars == CHARS("integer") ? integer_formatter
        : name_chars == CHARS("decimal") ? decimal_formatter
        : name_chars == CHARS("currency") ? currency_formatter
        : name_chars == CHARS("date") ? date_formatter
        : name_chars == CHARS("date-local") ? date_local_formatter
        : name_chars == CHARS("time") ? time_formatter
        : name_chars == CHARS("time-local") ? time_local_formatter
        : name_chars == CHARS("enum") ? enum_formatter
        : name_chars == CHARS("duration") ? duration_formatter
        : simple_formatter;
    return result;
}

volatile aux::chars aux_text = CHARS("text");
volatile aux::chars aux_integer = CHARS("integer");
volatile aux::chars aux_decimal = CHARS("decimal");
volatile aux::chars aux_currency = CHARS("currency");
volatile aux::chars aux_date = CHARS("date");
volatile aux::chars aux_datelocal = CHARS("date-local");
volatile aux::chars aux_time = CHARS("time");
volatile aux::chars aux_timelocal = CHARS("time-local");
volatile aux::chars aux_enum = CHARS("enum");
volatile aux::chars aux_duration = CHARS("duration");

FormatterType if_t2e_disable_opt(const std::string& name)
{
    aux::chars name_chars = aux::chars_of(name);
    return name_chars == aux_text ? simple_formatter
        : name_chars == aux_integer ? integer_formatter
        : name_chars == aux_decimal ? decimal_formatter
        : name_chars == aux_currency ? currency_formatter
        : name_chars == aux_date ? date_formatter
        : name_chars == aux_datelocal ? date_local_formatter
        : name_chars == aux_time ? time_formatter
        : name_chars == aux_timelocal ? time_local_formatter
        : name_chars == aux_enum ? enum_formatter
        : name_chars == aux_duration ? duration_formatter
        : simple_formatter;
}

std::vector<std::pair<std::string, FormatterType>> vector_string_no_order = {
    std::pair<std::string,FormatterType> { "text", simple_formatter },
    std::pair<std::string,FormatterType> { "integer", integer_formatter },
    std::pair<std::string,FormatterType> { "decimal", decimal_formatter },
    std::pair<std::string,FormatterType> { "currency", currency_formatter },
    std::pair<std::string,FormatterType> { "date", date_formatter },
    std::pair<std::string,FormatterType> { "date-local", date_local_formatter },
    std::pair<std::string,FormatterType> { "time", time_formatter },
    std::pair<std::string,FormatterType> { "time-local", time_local_formatter },
    std::pair<std::string,FormatterType> { "enum", enum_formatter },
    std::pair<std::string,FormatterType> { "duration", duration_formatter }
};

std::vector<std::pair<std::string, FormatterType>> vector_string_order = {
    std::pair<std::string,FormatterType> { "text", simple_formatter },
    std::pair<std::string,FormatterType> { "date", date_formatter },
    std::pair<std::string,FormatterType> { "time", time_formatter },
    std::pair<std::string,FormatterType> { "enum", enum_formatter },
    std::pair<std::string,FormatterType> { "integer", integer_formatter },
    std::pair<std::string,FormatterType> { "decimal", decimal_formatter },
    std::pair<std::string,FormatterType> { "currency", currency_formatter },
    std::pair<std::string,FormatterType> { "duration", duration_formatter },
    std::pair<std::string,FormatterType> { "date-local", date_local_formatter },
    std::pair<std::string,FormatterType> { "time-local", time_local_formatter },
};

std::vector<std::pair<aux::chars, FormatterType>> vector_slice_no_order = {
    std::pair<aux::chars,FormatterType> { CHARS("text"), simple_formatter },
    std::pair<aux::chars,FormatterType> { CHARS("integer"), integer_formatter },
    std::pair<aux::chars,FormatterType> { CHARS("decimal"), decimal_formatter },
    std::pair<aux::chars,FormatterType> { CHARS("currency"), currency_formatter },
    std::pair<aux::chars,FormatterType> { CHARS("date"), date_formatter },
    std::pair<aux::chars,FormatterType> { CHARS("date-local"), date_local_formatter },
    std::pair<aux::chars,FormatterType> { CHARS("time"), time_formatter },
    std::pair<aux::chars,FormatterType> { CHARS("time-local"), time_local_formatter },
    std::pair<aux::chars,FormatterType> { CHARS("enum"), enum_formatter },
    std::pair<aux::chars,FormatterType> { CHARS("duration"), duration_formatter }
};

std::vector<std::pair<aux::chars, FormatterType>> vector_slice_order = {
    std::pair<aux::chars,FormatterType> { CHARS("text"), simple_formatter },
    std::pair<aux::chars,FormatterType> { CHARS("date"), date_formatter },
    std::pair<aux::chars,FormatterType> { CHARS("time"), time_formatter },
    std::pair<aux::chars,FormatterType> { CHARS("enum"), enum_formatter },
    std::pair<aux::chars,FormatterType> { CHARS("integer"), integer_formatter },
    std::pair<aux::chars,FormatterType> { CHARS("decimal"), decimal_formatter },
    std::pair<aux::chars,FormatterType> { CHARS("currency"), currency_formatter },
    std::pair<aux::chars,FormatterType> { CHARS("duration"), duration_formatter },
    std::pair<aux::chars,FormatterType> { CHARS("date-local"), date_local_formatter },
    std::pair<aux::chars,FormatterType> { CHARS("time-local"), time_local_formatter },
};

FormatterType search_vector_string_no_order(const std::string& name)
{
    auto it = std::find_if(vector_string_no_order.begin(), vector_string_no_order.end(),
        [&name](const std::pair<std::string, FormatterType>& p) { return name == p.first; });

    return (it != vector_string_no_order.end()) ? it->second : simple_formatter;
}

FormatterType search_vector_string_order(const std::string& name)
{
    for (auto& value : vector_string_order)
    {
        if (value.first == name) return value.second;
    }

    return simple_formatter;
}

FormatterType search_vector_slice_no_order(const std::string& name)
{
    aux::chars name_chars = aux::chars_of(name);

    for (auto& value : vector_slice_no_order)
    {
        if (value.first == name_chars) return value.second;
    }

    return simple_formatter;
}

FormatterType search_vector_slice_order(const std::string& name)
{
    aux::chars name_chars = aux::chars_of(name);

    for (auto& value : vector_slice_order)
    {
        if (value.first == name_chars) return value.second;
    }

    return simple_formatter;
}

int main(int argc, char *argv[])
{
    generate_input();

    auto start = std::chrono::steady_clock::now();
    unsigned tn = 0;
    for (int n = 0; n < TOTAL_RUNS; ++n)
        for (int i = 0; i < TOTAL_RUNS; ++i)
            tn += (unsigned)if_t2e(input[i]);
    auto finish = std::chrono::steady_clock::now();
    double elapsed_seconds = std::chrono::duration_cast<std::chrono::duration<double> >(finish - start).count();

    std::cout << "if_t2e" << " " << elapsed_seconds << " " << tn << std::endl;

    start = std::chrono::steady_clock::now();
    tn = 0;
    for (int n = 0; n < TOTAL_RUNS; ++n)
        for (int i = 0; i < TOTAL_RUNS; ++i)
            tn += (unsigned)if_t2e_disable_opt(input[i]);
    finish = std::chrono::steady_clock::now();
    elapsed_seconds = std::chrono::duration_cast<std::chrono::duration<double> >(finish - start).count();

    std::cout << "if_t2e_disable_opt  " << elapsed_seconds << " " << tn << std::endl;


    start = std::chrono::steady_clock::now();
    tn = 0;
    for (int n = 0; n < TOTAL_RUNS; ++n)
        for (int i = 0; i < TOTAL_RUNS; ++i)
            tn += (unsigned)search_vector_string_no_order(input[i]);
    finish = std::chrono::steady_clock::now();
    elapsed_seconds = std::chrono::duration_cast<std::chrono::duration<double> >(finish - start).count();

    std::cout << "search_vector_string_no_order " << elapsed_seconds << " " << tn << std::endl;


    start = std::chrono::steady_clock::now();
    tn = 0;
    for (int n = 0; n < TOTAL_RUNS; ++n)
        for (int i = 0; i < TOTAL_RUNS; ++i)
            tn += (unsigned)search_vector_string_order(input[i]);
    finish = std::chrono::steady_clock::now();
    elapsed_seconds = std::chrono::duration_cast<std::chrono::duration<double> >(finish - start).count();

    std::cout << "search_vector_string_order " << elapsed_seconds << " " << tn << std::endl;


    start = std::chrono::steady_clock::now();
    tn = 0;
    for (int n = 0; n < TOTAL_RUNS; ++n)
        for (int i = 0; i < TOTAL_RUNS; ++i)
            tn += (unsigned)search_vector_slice_no_order(input[i]);
    finish = std::chrono::steady_clock::now();
    elapsed_seconds = std::chrono::duration_cast<std::chrono::duration<double> >(finish - start).count();

    std::cout << "search_vector_slice_no_order " << elapsed_seconds << " " << tn << std::endl;


    start = std::chrono::steady_clock::now();
    tn = 0;
    for (int n = 0; n < TOTAL_RUNS; ++n)
        for (int i = 0; i < TOTAL_RUNS; ++i)
            tn += (unsigned)search_vector_slice_order(input[i]);
    finish = std::chrono::steady_clock::now();
    elapsed_seconds = std::chrono::duration_cast<std::chrono::duration<double> >(finish - start).count();

    std::cout << "search_vector_slice_order " << elapsed_seconds << " " << tn << std::endl;


    return 0;
}


А вот результаты:
  Результатики

VS 2015:
if_t2e 2.06238 359490000
if_t2e_disable_opt 2.58692 359490000
search_vector_string_no_order 6.19423 359490000
search_vector_string_order 6.65881 359490000
search_vector_slice_no_order 4.20195 359490000
search_vector_slice_order 3.93327 359490000


[root@server tests]# ./run-4.9.2.sh
if_t2e 1.26558 359540000
if_t2e_disable_opt 1.99513 359540000
search_vector_string_no_order 2.27271 359540000
search_vector_string_order 2.45472 359540000
search_vector_slice_no_order 1.86913 359540000
search_vector_slice_order 1.98669 359540000

[root@server tests]# ./run-5.3.0.sh
if_t2e 1.17153 359540000
if_t2e_disable_opt 2.02901 359540000
search_vector_string_no_order 2.25595 359540000
search_vector_string_order 2.35924 359540000
search_vector_slice_no_order 1.89309 359540000
search_vector_slice_order 1.89116 359540000

[root@server tests]# ./run-6.1.0.sh
if_t2e 1.0725 359540000
if_t2e_disable_opt 1.97939 359540000
search_vector_string_no_order 2.3664 359540000
search_vector_string_order 2.43029 359540000
search_vector_slice_no_order 1.90254 359540000
search_vector_slice_order 1.93222 359540000


Вот теперь, попытка интерпретации результатов.
Что мы имеем.


"Банальный поиск" выигрывает у поиска по std::string в std::vector и у slice в std::vector.

"Банальный поиск" в результате превращается в оптимизированный вариант сравнения с констатами.
Оптимизированный, потому что строки выклаюыватся по длине в определенным образом.
Сравнение с константами, потому что компилятор может их подставить.

Давай-те попробуем усложнить задачу, и попробовать запретить подстановку строк с помощью volatile ( пришлось дописать конструктор с volatile ).
И увидим, что if_t2e_disable_opt уже выросла в почти 2 раза ( и равно обычному линейном поиску в std::vector для slice ),
что подталкивает не мысль, что обращение к памяти ( или кешу, тут уже не знаю ) ухудшает работу.

Но все равно поиск по строкам занимает больше времени.
Если взглянуть на реализацию сравнения std::string и slice мы увидим, что:
slice делает меньше телодвижений ( сравнивается только длина и значения )
std::string делает больше работы ( во всяком случае под дебагом в VS ):
1. Есть сравнение длинны строки ( из за SSO оптимизации ) это раз.
2. Сравнение реализовано через int compare, т.е результат может быть "равно" , "больше", "меньше",
а это требует, как минимум еще одного сравнения длинны. И только потом уже мы можем перейти непосредсвенно к сравнению строк.
Похоже, что на 10,000,000 итерации эти несколько "лишних" сравнений и ухудшают результат.
Это кстати ответ, на вопрос в вашем другом посте ( в чем разница, между хранением std::string и slice: короткий ответ в реализации operator==)

А вот ручное выкладывание строк по порядку, результато не дало.
Отредактировано 17.10.2017 9:12 Engler . Предыдущая версия .
Re[2]: Когда linear search быстрее hash map
От: Engler Беларусь  
Дата: 17.10.17 13:42
Оценка:
Здравствуйте, alex_public, Вы писали:

_>Хм, я тебе вроде как всё понятно разъяснил в этом http://rsdn.org/forum/cpp/6934121.1
Автор: alex_public
Дата: 15.10.17
 сообщение той темки. Непонятно зачем ты завёл новую. Разве что хотелось ещё поговорить об этом, но нечего было ответить на то сообщение? )))

Можно вопрос, std::string_view , как раз использует лексикографический порядок, http://en.cppreference.com/w/cpp/string/basic_string_view/operator_cmp. Или я что-то упускаю? Каким способом можно еще сравнить строки, если не лексикографическим порядком (всмысле, как сделать операцию < еще легче)?
Re[3]: Когда linear search быстрее hash map
От: alex_public  
Дата: 19.10.17 21:24
Оценка:
Здравствуйте, Engler, Вы писали:

_>>Хм, я тебе вроде как всё понятно разъяснил в этом http://rsdn.org/forum/cpp/6934121.1
Автор: alex_public
Дата: 15.10.17
 сообщение той темки. Непонятно зачем ты завёл новую. Разве что хотелось ещё поговорить об этом, но нечего было ответить на то сообщение? )))
E>Можно вопрос, std::string_view , как раз использует лексикографический порядок, http://en.cppreference.com/w/cpp/string/basic_string_view/operator_cmp. Или я что-то упускаю?

И у std::string и у std::string_view оператор сравнения является лексикографическим, о чём я собственно и написал в сообщение по ссылке выше. Однако std::map совершенно не обязан его использовать — это всего лишь значение по умолчанию для 3-го параметра шаблона map, который в случае принципиальности быстродействия естественно устанавливается свой.

E>Каким способом можно еще сравнить строки, если не лексикографическим порядком (всмысле, как сделать операцию < еще легче)?

Да как угодно, лишь бы работал быстро и позволял реализовывать некую сортировку. Например по ссылке выше есть рабочий пример подобного оператора, с которым std::map работает быстрее линейного поиска даже на маленьких перечислениях.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.