LPCSTR pTest1 = "http://www.boressoft.ru:80/cgi-bin/text.cgi?test=1&text=2";
LPCSTR pTest2 = "http://www.boressoft.ru:80/cgi-bin/text.cgi?test=1&text=2";
for (USHORT i = 0; i < 65500; i++)
{
strnlen(pTest1, _MAX_PATH);
strcmp(pTest1, pTest2);
strlen(pTest1);
}
return 0;
И замерил время выполнения (edge time) при помощи Intel VTune 8.0:
strlen — 3 306
strcmp — 7 443
strnlen — 16 292
Кто-нибудь может мне объяснить, что такого там делает strnlen, что по времени выполнения она проигрывает даже strcmp, которой надо не просто бежать по строке, а ещё и сравнивать с другой строкой?
F11 использовать не разрешают?
strnlen работает побайтно, strlen по-4-байтно (на x86), первый просто ещё не оптимирован
В 4 раза меньше прыжков — хорошо для конвеера.
Re: Время выполнения strnlen (VS2005)
От:
Аноним
Дата:
05.11.06 18:48
Оценка:
Здравствуйте, BoresExpress, Вы писали:
strlen может intrinsic, а strnlen — вроде нет.
ИМХО: К реальной поизводительности реальных программ такие тесты не имеют ни малейшего отношения — попусту тратите своё время.
Здравствуйте, BoresExpress, Вы писали:
BE>Кто-нибудь может мне объяснить, что такого там делает strnlen, что по времени выполнения она проигрывает даже strcmp, которой надо не просто бежать по строке, а ещё и сравнивать с другой строкой?
BE>Дорогая какая-то буква n получается...
На абсолютную истину не претендую, но в ...n... варианте кроме всего прочего нужно еще и n на каждой итерации проверять
Здравствуйте, Аноним, Вы писали:
А>ИМХО: К реальной поизводительности реальных программ такие тесты не имеют ни малейшего отношения — попусту тратите своё время.
Мда?
Вот вам ситуация. У меня в программе много сравнений строк. Но в подавляющем большинстве случаев, длина строк — разная. Я решил оптимизировать операцию сравнения, добавив перед strcmp вызов strlen и сравнение её результата с сохранённой длиной первой строки. Это действительно увеличило производительность, посколько, как вы можете видеть из моего сообщения, время работы strlen заметно меньше, чем у strcmp.
Вы считаете, что это всё фигня? Объясните, пожалуйста, почему.
Здравствуйте, BoresExpress, Вы писали:
BE>Здравствуйте, Аноним, Вы писали:
А>>ИМХО: К реальной поизводительности реальных программ такие тесты не имеют ни малейшего отношения — попусту тратите своё время.
BE>Мда?
BE>Вот вам ситуация. У меня в программе много сравнений строк. Но в подавляющем большинстве случаев, длина строк — разная. Я решил оптимизировать операцию сравнения, добавив перед strcmp вызов strlen и сравнение её результата с сохранённой длиной первой строки. Это действительно увеличило производительность, посколько, как вы можете видеть из моего сообщения, время работы strlen заметно меньше, чем у strcmp.
BE>Вы считаете, что это всё фигня? Объясните, пожалуйста, почему.
а много сравнений или происходит поиск строки?
а строки часто добавляются?
Вы оптимизируете программу, а может можно поменять алгоритм, что бы не было так много сравнений?
Здравствуйте, Сергей Мухин, Вы писали:
СМ>Здравствуйте, BoresExpress, Вы писали:
BE>>Здравствуйте, Аноним, Вы писали:
А>>>ИМХО: К реальной поизводительности реальных программ такие тесты не имеют ни малейшего отношения — попусту тратите своё время.
BE>>Мда?
BE>>Вы считаете, что это всё фигня? Объясните, пожалуйста, почему.
СМ>а много сравнений или происходит поиск строки?
Много сравнений. Есть база URL и в ней ищется совпадения с заданным URL.
СМ>а строки часто добавляются?
В базу? Редко. При перезагрузке конфигурации.
СМ>Вы оптимизируете программу, а может можно поменять алгоритм, что бы не было так много сравнений?
Не выйдет. URL — это строка, и никакого другого способа проверки URL по базе я не вижу.
Здравствуйте, BoresExpress, Вы писали:
BE>Здравствуйте, Сергей Мухин, Вы писали:
СМ>>а много сравнений или происходит поиск строки? BE>Много сравнений. Есть база URL и в ней ищется совпадения с заданным URL.
Именно совпадения? Не поиск по шаблону?
Тогда может, можно отсортировать/проиндексировать?
СМ>>а строки часто добавляются? BE>В базу? Редко. При перезагрузке конфигурации. СМ>>Вы оптимизируете программу, а может можно поменять алгоритм, что бы не было так много сравнений? BE>Не выйдет. URL — это строка, и никакого другого способа проверки URL по базе я не вижу.
Если сравнивать полностью строку, можно при загрузке базы некую числовую характеристику к строкам добавлять. Хэш какой-нибудь, или на худой конец ту же длину. Ну а дальше — числа разные — строки точно не равны, числа одниковые — тогда сравниваем строки.
Здравствуйте, superlexx, Вы писали:
S>F11 использовать не разрешают? S>strnlen работает побайтно, strlen по-4-байтно (на x86), первый просто ещё не оптимирован S>В 4 раза меньше прыжков — хорошо для конвеера.
Действительно, всё тупо:
size_t __cdecl strnlen(const char *str, size_t maxsize)
{
size_t n;
/* Note that we do not check if s == NULL, because we do not
* return errno_t...
*/for (n = 0; n < maxsize && *str; n++, str++)
;
return n;
}
Спасибо за ответ.
Re[3]: Время выполнения strnlen (VS2005)
От:
Аноним
Дата:
07.11.06 10:20
Оценка:
Здравствуйте, BoresExpress, Вы писали:
BE>Вот вам ситуация. У меня в программе много сравнений строк. Но в подавляющем большинстве случаев, длина строк — разная. Я решил оптимизировать операцию сравнения, добавив перед strcmp вызов strlen и сравнение её результата с сохранённой длиной первой строки. Это действительно увеличило производительность, посколько, как вы можете видеть из моего сообщения, время работы strlen заметно меньше, чем у strcmp.
BE>Вы считаете, что это всё фигня? Объясните, пожалуйста, почему.
Ну, в вашем специфическом случае — наверное нет.
Здравствуйте, alexqc, Вы писали:
A>Здравствуйте, BoresExpress, Вы писали:
BE>>Здравствуйте, Сергей Мухин, Вы писали:
СМ>>>а много сравнений или происходит поиск строки? BE>>Много сравнений. Есть база URL и в ней ищется совпадения с заданным URL.
A>Именно совпадения? Не поиск по шаблону?
Именно совпадений.
A>Тогда может, можно отсортировать/проиндексировать?
Как раз сейчас тестирую вариант с сортировкой.
СМ>>>а строки часто добавляются? BE>>В базу? Редко. При перезагрузке конфигурации. СМ>>>Вы оптимизируете программу, а может можно поменять алгоритм, что бы не было так много сравнений? BE>>Не выйдет. URL — это строка, и никакого другого способа проверки URL по базе я не вижу.
A>Если сравнивать полностью строку, можно при загрузке базы некую числовую характеристику к строкам добавлять. Хэш какой-нибудь, или на худой конец ту же длину. Ну а дальше — числа разные — строки точно не равны, числа одниковые — тогда сравниваем строки.
Вот я так и делаю! Для строк в базе у меня хранится длина, для строк извне я считаю длину и сравниваю сначала её. Именно тут я и обнаружил, что strnlen работает медленее, чем strlen.
Но господин Аноним, почему-то, сказал мне, что на реальную производительность время выполенния str(n)len не влияет. Я пытаюсь понять почему.
Здравствуйте, BoresExpress, Вы писали:
BE>Здравствуйте, Сергей Мухин, Вы писали:
СМ>>Вы оптимизируете программу, а может можно поменять алгоритм, что бы не было так много сравнений?
BE>Не выйдет. URL — это строка, и никакого другого способа проверки URL по базе я не вижу.
ну как это не выйдет! есть целые книги, описывающие алгоритмы поиска, а Вы сразу — не выйдет. т.е. Вы уже нашли наилучший алгоритм поиска?
тут не раскрывается слово "база". Это что. SQL? если нет, то как делается поиск по базе? мб отсортировать или еще как.
маленький вопрос, судя по именам ф-ям тут UNICODE и не пахнет, это такой проект?
Здравствуйте, Сергей Мухин, Вы писали:
СМ>тут не раскрывается слово "база". Это что. SQL? если нет, то как делается поиск по базе? мб отсортировать или еще как.
Это список строк. В каждом списке только строки, ничинающиеся на одну букву.
Список отсортирован, поэтому для того, чтобы понять, есть ли искомая строка в списке или нет, весь список просматривать не надо.
СМ>маленький вопрос, судя по именам ф-ям тут UNICODE и не пахнет, это такой проект?
Это http://sf.net/projects/sito
ISA Server даёт все строки в ANSI, что логично, т.к. на многоязычную систему доменных имён мы ещё не перешли (некоторые отщепенцы не в счтёт).
Здравствуйте, BoresExpress, Вы писали:
BE>Здравствуйте, Сергей Мухин, Вы писали:
СМ>>тут не раскрывается слово "база". Это что. SQL? если нет, то как делается поиск по базе? мб отсортировать или еще как.
BE>Это список строк. В каждом списке только строки, ничинающиеся на одну букву.
наверно все на W
BE>Список отсортирован, поэтому для того, чтобы понять, есть ли искомая строка в списке или нет, весь список просматривать не надо.
т.е., если я правильно понял, у Вас алгоритм O(log N)
Здравствуйте, Сергей Мухин, Вы писали:
BE>>Это список строк. В каждом списке только строки, ничинающиеся на одну букву.
СМ>наверно все на W
Нет. Во-первых, не все домены ничинаются на www. Во-вторых, домен разбивается на секии (по точке) и по этому строится дерево.
Так что на первом уровне на w пожалуй только ws.
BE>>Список отсортирован, поэтому для того, чтобы понять, есть ли искомая строка в списке или нет, весь список просматривать не надо.
СМ>т.е., если я правильно понял, у Вас алгоритм O(log N)
СМ>А каков порядок длины этого списка строк?
Списков ровно 36 (26 букв + 10 цифр) в каждом узле дерева. Самые большие списки на первом уровне (например, дети узла com или ru). Там бавает несколько десятков тысяч строк, но они более-менее равномерно распередены между буквами.
Здравствуйте, BoresExpress, Вы писали:
BE>Нет. Во-первых, не все домены ничинаются на www. Во-вторых, домен разбивается на секии (по точке) и по этому строится дерево. BE>Так что на первом уровне на w пожалуй только ws.
BE>>>Список отсортирован, поэтому для того, чтобы понять, есть ли искомая строка в списке или нет, весь список просматривать не надо.
СМ>>т.е., если я правильно понял, у Вас алгоритм O(log N)
СМ>>А каков порядок длины этого списка строк?
BE>Списков ровно 36 (26 букв + 10 цифр) в каждом узле дерева. Самые большие списки на первом уровне (например, дети узла com или ru). Там бавает несколько десятков тысяч строк, но они более-менее равномерно распередены между буквами.
1. попробуйте второе имя поставить первым, оно более равномерно ИМХО
2. если 10000, и алгоритм O(logN) то получается где-то 13 сравнений за один поиск, надо ли это оптимизировать? Сколько запросов в сек?
Здравствуйте, BoresExpress, Вы писали:
BE>Списков ровно 36 (26 букв + 10 цифр) в каждом узле дерева. Самые большие списки на первом уровне (например, дети узла com или ru). Там бавает несколько десятков тысяч строк, но они более-менее равномерно распередены между буквами.
Борис, в URI могут встречаться не только латинские буквы и цифры — rfc1808
ещё ";" | "?" ":" | "@" | "&" | "=" | "$" | "-" | "_" | "." | "+" | "!" | "*" | "'" | "(" | ")" | ","
и, вообще говоря, любой другой символ, включая "\0" в виде escape-последовательности, и по-хорошему в фильтре http адресов их надо преобразовывать, т.к.
For example, the following three URIs are equivalent:
Здравствуйте, Сергей Мухин, Вы писали:
СМ>1. попробуйте второе имя поставить первым, оно более равномерно ИМХО
При добавлениях в телефонных базах переворачивают номера телефонов задом-наперёд, тогда "близкие" номера получаются далеко, и вставки идут в разные сегменты... к чему это я... может чем пригодится
Здравствуйте, remark, Вы писали:
R>Здравствуйте, BoresExpress, Вы писали:
BE>>Списков ровно 36 (26 букв + 10 цифр) в каждом узле дерева. Самые большие списки на первом уровне (например, дети узла com или ru). Там бавает несколько десятков тысяч строк, но они более-менее равномерно распередены между буквами.
R>... в URI могут встречаться не только латинские буквы и цифры ...
Здравствуйте, BoresExpress, Вы писали:
СМ>>тут не раскрывается слово "база". Это что. SQL? если нет, то как делается поиск по базе? мб отсортировать или еще как. BE>Это список строк. В каждом списке только строки, ничинающиеся на одну букву. BE>Список отсортирован, поэтому для того, чтобы понять, есть ли искомая строка в списке или нет, весь список просматривать не надо.
Погугли насчёт trie-деревьев — Похоже это именно то, что тебе надо.
