Скорость сравнения строк в Ansi и Unicode формате.

← →
Riply © (2007-10-31 03:51) [0]

Здравствуйте !
Допустим, у нас есть две строки:
wBuf1, wBuf2: WideString;
и они же, "переведенные в Ansi": aBuf1, aBuf2: string;
Верно ли следующее утверждение:
регистро-зависимое сравнение aBuf1 и aBuf2 будет выполняться быстрее,
чем регистро-зависимое сравнение wBuf1 и wBuf2 ?

← →
guav © (2007-10-31 10:56) [1]

В общем, быстрее или медленнее может быть какая-либо конкретная реализация сравнения, а не сравнение вообще.
Можно порассуждать о возможной реализации.
Если считать что регистрозависимое сравнение - это сравнение памяти, то если длина известна и используется, то может быть быстрее анси версия, там этой сравниваемой памяти меньше, а если длина не известна, то сравнение должно осуществлятся по одному символу, чтобы искать #0 в процессе сравнения, тогда сравнивать число сравнений одинаково, потому и скорость может быть (почти) одинакова.
Сравнение может и не быть побайтным сравнением. Например, если при сравненни учитывать, что в Unicode у некоторых символов моет быть много форм, и сравнение не должно давать разные результаты, или если сравнение используется для сортировки, то возможно прийдётся рассматривать Ansi строку как возможно мультибайтную и сравнивать положения символов в конкретном алфавите.

Короче говоря, если требуется знать точно - то единственный выход - провести измерения.

← →
Reindeer Moss Eater © (2007-10-31 11:12) [2]

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

← →
Riply © (2007-10-31 11:49) [3]

> [1] guav © (31.10.07 10:56)
> Если считать что регистрозависимое сравнение - это сравнение памяти, то если длина известна и используется,
>то может быть быстрее анси версия, там этой сравниваемой памяти меньше, а если длина не известна,
>то сравнение должно осуществлятся по одному символу, чтобы искать #0 в процессе сравнения,
>тогда сравнивать число сравнений одинаково, потому и скорость может быть (почти) одинакова.

Примерно так же я и начала рассуждать и застопорилась.

> [2] Reindeer Moss Eater © (31.10.07 11:12)
> Куски памяти могут быть разные, а стороки ими представленные будут фактически одни и те же.
К своему стыду, вынуждена признать, что это для меня открытие :(

P.S.
Придется покопаться в ReactOS. Иногда там можно найти ответы на подобные вопросы.

← →
Anatoly Podgoretsky © (2007-10-31 13:11) [4]

> Reindeer Moss Eater (31.10.2007 11:12:02) [2]

Если не брать разные платформы, но никаких других форм не существует.

← →
Anatoly Podgoretsky © (2007-10-31 13:14) [5]

> Riply (31.10.2007 03:51:00) [0]

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

← →
Riply © (2007-10-31 14:27) [6]

>[4] Anatoly Podgoretsky © (31.10.07 13:11)
> Если не брать разные платформы, но никаких других форм не существует.

Это радует :)

> [5] Anatoly Podgoretsky © (31.10.07 13:14)
> Думаешь сравнение байта по сравнению со словом сильно отличается по скорости

Нет, я исходила из того, что в результате нужно сравнивать "меньший объем памяти :"
Например, если используется CompareMem :)

P.S.
Если кому интересно...

CompareStringA работает через CompareStringW,
которая, в свою очередь, использует RtlCompareUnicodeString.

Реализации RtlCompareString и RtlCompareUnicodeString ничем не отличаются.
Т.е. никакого учета "других форм" там нет. (Или я не умею смотреть)
(сравнение посимвольное)

← →
clickmaker © (2007-10-31 14:29) [7]

> Реализации RtlCompareString и RtlCompareUnicodeString ничем
> не отличаются.

а с чего бы? если windows nt насквозь уникодная

← →
Riply © (2007-10-31 14:32) [8]

> [7] clickmaker © (31.10.07 14:29)
> а с чего бы? если windows nt насквозь уникодная

Имелось ввиду что не рассматриваются варианты
"что один и тот же символ может быть представлен разными способами".

← →
Anatoly Podgoretsky © (2007-10-31 14:35) [9]

> Например, если используется CompareMem :)

Шурик это не наш метод.

← →
Anatoly Podgoretsky © (2007-10-31 14:36) [10]

Я имею в виду, что если CompareMem, то надо заменить на свою функцию, которая сравнивает четыре байта за раз.

← →
guav © (2007-10-31 14:51) [11]

> [10] Anatoly Podgoretsky © (31.10.07 14:36)

А разве стандартная CompareMem таковой не является ?

> Если не брать разные платформы, но никаких других форм не
> существует.

То есть ?
http://ru.wikipedia.org/wiki/%D0%AE%D0%BD%D0%B8%D0%BA%D0%BE%D0%B4#.D0.9C.D0.BE.D0.B4.D0.B8.D1.84.D0.B8.D1.86.D0.B8.D1.80.D1.83.D1.8E.D1.89.D0.B 8.D0.B5_.D1.81.D0.B8.D0.BC.D0.B2.D0.BE.D0.BB.D1.8B - разве это не едино для всех платформ ?

← →
Anatoly Podgoretsky © (2007-10-31 16:20) [12]

Мне неизвестно внутреннее устройство CompareMem

← →
clickmaker © (2007-10-31 17:17) [13]

> [12] Anatoly Podgoretsky © (31.10.07 16:20)

SysUtils.pas

← →
Riply © (2007-10-31 17:25) [14]

> [13] clickmaker © (31.10.07 17:17)
> SysUtils.pas
А можно "на пальцах" для тех, кто в ассемблере "как в апельсинах" ?

← →
clickmaker © (2007-10-31 17:36) [15]

> [14] Riply © (31.10.07 17:25)

REPE CMPSD
JNE @@2
MOV ECX,EDX
REPE CMPSB
JNE @@2
@@1: INC EAX
@@2: POP EDI

сравнение в 2 приема: сначала 4 байта, потом оставшиеся 2
так что 32-битная логика задействована

← →
Riply © (2007-10-31 17:46) [16]

> [15] clickmaker © (31.10.07 17:36)
Спасибо.

← →
clickmaker © (2007-10-31 17:55) [17]

> потом оставшиеся 2

тьфу, оставшиеся от 1 до 3, разумеется )

← →
Anatoly Podgoretsky © (2007-10-31 19:26) [18]

> clickmaker (31.10.2007 17:36:15) [15]

Это хорошо, но в тоже время задействована медленная аггрегатная команда REPE CMPSD

← →
guav © (2007-10-31 21:26) [19]

> медленная аггрегатная команда REPE CMPSD

Ну если так придиратся то стоит заглянуть на http://fastcode.sourceforge.net/ :)

И всё таки, разве различные формы не существуют ?
Откуда такая информация:

> Anatoly Podgoretsky © (31.10.07 13:11) [4]

> Если не брать разные платформы, но никаких других форм не
> существует.

← →
Anatoly Podgoretsky © (2007-10-31 21:57) [20]

> guav (31.10.2007 21:26:19) [19]

Уважаю этот ресурс.
А насчет разных форм сболтнул кто то некомпетентный, на текущий момент есть только две формы ucs-2 и ucs-4 и других не предвидится.
При том смешно, когда Микрософт продвигал ucs-4 над ним смеялось сообщество ucs-2 и утверждало, что только ucs-2 а ucs-4 это ересь. Когда же Микрософт стал использовать ucs-2, то же самое сообщество стало использовать то чего обсмеивало.

← →
guav © (2007-10-31 22:06) [21]

> А насчет разных форм сболтнул кто то некомпетентный, на
> текущий момент есть только две формы ucs-2 и ucs-4 и других
> не предвидится.

Речь идёт о композиции и декомпозиции
Например, символ «á» может быть представлен как последовательность базового символа «a» (U+0061) и модифицирующего символа « ́» (U+0301) или как монолитный символ «á» (U+00C1).

Насчёт кодирования, читал в википедиии что в современных Windows Юникод не ucs-2, а UTF-16, просто зарезервинованные символы ucs-2 делоют её подмножетсвом UTF-16. В MSDN подтверждение не искал, пока не этот вопрос беспокоит.

← →
Anatoly Podgoretsky © (2007-10-31 22:12) [22]

> guav (31.10.2007 22:06:21) [21]

Давай не будем говорить о транспортной кодировке, к Юникод это имеет только косвенное отношеие.

← →
guav © (2007-10-31 22:30) [23]

> Давай не будем говорить о транспортной кодировке, к Юникод
> это имеет только косвенное отношеие.

Давай будем говорить о кодировке, используемой в W-функциях.

http://msdn2.microsoft.com/en-us/library/ms776459.aspx
Unicode-enabled functions are often referred to as wide character functions, as described in Conventions for Function Prototypes. This designation is made because of the use of the UTF-16 encoding, which is the most common encoding of Unicode and the one used for native Unicode encoding on Windows operating systems. Each code value is 16 bits wide, in contrast to the older code page approach to character and string data, which uses 8-bit code values.

← →
guav © (2007-10-31 22:31) [24]

И оттуда же
Unicode can often represent the same glyph in either a ""composed"" or a ""decomposed"" form: for example, the composed form of "Ä" is the single Unicode code point "Ä" (U+00C4), while its decomposed form is "A" + "¨" (U+0041 U+0308).

То есть CompareMem не всегда будет работать как требуется.

← →
Anatoly Podgoretsky © (2007-10-31 22:55) [25]

Лучше взлянуть вот эту статью http://en.wikipedia.org/wiki/UTF-16
В ней более подробно описана эта запутаная ситуация с Юникод.

← →
guav © (2007-10-31 23:07) [26]

В любом случае само мультибайтоное представление UTF-16 не помешает CompareMem, в [2] говорилось именно о формах, а не о кодировках.

← →
Anatoly Podgoretsky © (2007-10-31 23:08) [27]

> guav (31.10.2007 23:07:26) [26]

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

← →
Riply © (2007-10-31 23:12) [28]

Что-то я не понимаю. Совсем запуталась. :(
Microsoft, если я правильно увидела, сравнивает так: wBuf1[i] = wBuf2[i].
Вы хотите сказать, что равенство может быть верным, при разной "памяти" wBuf1 и wBuf2 ?

← →
Anatoly Podgoretsky © (2007-10-31 23:19) [29]

> Что-то я не понимаю. Совсем запуталась

Не ты первая.

← →
Riply © (2007-10-31 23:21) [30]

> [29] Anatoly Podgoretsky © (31.10.07 23:19)

>Не ты первая.

Мне от этого не легче :))

← →
Anatoly Podgoretsky © (2007-10-31 23:25) [31]

> Riply (31.10.2007 23:21:30) [30]

А кому сейчас легко.

← →
DevilDevil (2007-10-31 23:32) [32]

function EqualStrings(const S1, S2 : string) : integer; begin Result := (integer(S1) = integer(S2)) or ( Length(S1) = Length(S2) and CompareMem(pointer(S1), pointer(S2), Length(S2) ) ); end;

а вообще, я писал такую же, только быстрее - полностью на ассемблере.

P.S. в FastCode вообще маньяки !!!

← →
guav © (2007-11-01 00:07) [33]

> Microsoft, если я правильно увидела, сравнивает так: wBuf1[i] = wBuf2[i].

где ?

PS: Так они вряд ли сравнивают, скорее они так копируют :)

← →
Джо © (2007-11-01 06:56) [34]

> [32] DevilDevil (31.10.07 23:32)
> function EqualStrings(const S1, S2 : string) : integer;
> begin
> Result := (integer(S1) = integer(S2)) or
> ( Length(S1) = Length(S2)
> and
> CompareMem(pointer(S1), pointer(S2), Length(S2)
> ) );
> end;
>
> а вообще, я писал такую же, только быстрее - полностью на
> ассемблере.
>
> P.S. в FastCode вообще маньяки !!!

А как вот это вообще к теме относится?

← →
Riply © (2007-11-01 08:12) [35]

> [33] guav © (01.11.07 00:07)
>> Microsoft, если я правильно увидела, сравнивает так: wBuf1[i] = wBuf2[i].
> где ?
> PS: Так они вряд ли сравнивают, скорее они так копируют :)
LONG NTAPI RtlCompareUnicodeString( IN PCUNICODE_STRING s1, IN PCUNICODE_STRING s2, IN BOOLEAN CaseInsensitive) { unsigned int len; LONG ret = 0; LPCWSTR p1, p2; len = min(s1->Length, s2->Length) / sizeof(WCHAR); p1 = s1->Buffer; p2 = s2->Buffer; if (CaseInsensitive) { while (!ret && len--) ret = RtlUpcaseUnicodeChar(*p1++) - RtlUpcaseUnicodeChar(*p2++); } else { while (!ret && len--) ret = *p1++ - *p2++; } if (!ret) ret = s1->Length - s2->Length; return ret; }

Если я не сумела это правильно понять, то ухожу в монастырь. :)

← →
Riply © (2007-11-01 08:23) [36]

>[34] Джо © (01.11.07 06:56)

>> [32] DevilDevil (31.10.07 23:32)
>А как вот это вообще к теме относится?

В теме слово "строка" есть ? - Есть ! Слово "сравнить" есть ? - Есть !
"Так что тебе, собака, еще надо ?" (с) Иван Васильевич

:)

← →
Anatoly Podgoretsky © (2007-11-01 09:16) [37]

> Riply (01.11.2007 08:12:35) [35]

А чего не поняла?
Сравнение можно заменять вычитанием, можно даже XOR применить.

← →
Riply © (2007-11-01 09:30) [38]

> [37] Anatoly Podgoretsky © (01.11.07 09:16)
> А чего не поняла?
> Сравнение можно заменять вычитанием, можно даже XOR применить.
:)
Это был ответ на [33] guav ©, показывающий, что они все таки сравнивают и
никакие различные представления одного и того же символа не учитывают :)

← →
Anatoly Podgoretsky © (2007-11-01 09:50) [39]

> Riply (01.11.2007 09:30:38) [38]

Так я про UCS-2 и говорил, а в Википедия пишут другое, что мол UTF-16, а что на самом деле - является тайной, но по приведеному коду этого не видно.

← →
guav © (2007-11-01 09:55) [40]

Это именно код Windows ?
Хотя, да, так и сравнивают. Мне удалось создать разные файлы с именами "Ä" (U+00C4), и "A" + "¨" (U+0041 U+0308).

← →
Riply © (2007-11-01 09:58) [41]

> [39] Anatoly Podgoretsky © (01.11.07 09:50)
> Так я про UCS-2 и говорил, а в Википедия пишут другое, что мол UTF-16,
> а что на самом деле - является тайной, но по приведеному коду этого не видно.

Код, чесно говоря, не совсем Microsoft`овский.
Взят отсюда: http://www.reactos.org/generated/doxygen/d8/d16/unicode_8c-source.html
Но я не думаю, что в таком важном вопросе ReactOS`овцы
позволили себе вольный перевод или авторскую правку :)

> Так я про UCS-2 и говорил, а в Википедия пишут другое, что
> мол UTF-16, а что на самом деле - является тайной

Тайны нет, MSDN тоже утверждает что UTF-16.

Да. RtlCompareUnicodeString работает именно так.
.7C917800: 668B4D08 mov cx,[ebp][00008] .7C917804: 663B4D10 cmp cx,[ebp][00010] .7C917808: 74DE je .07C9177E8

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

> [43] guav © (01.11.07 11:03)

> Сравнение CompareMem а не по символам там нельзя применить,
> т.к. функция должа вернуть не просто равенство или неравенство.

Зато можно попробовать использовать RtlCompareMemory :)

> [44] Riply © (01.11.07 11:11)
> Зато можно попробовать использовать RtlCompareMemory :)

Но не нужно :), наверное.
Хотя внешне и кажется, что это "оптимизирует", но что-то здесь "не то".
Они же так не поступили.
Скорее всего мы начнем проигрывать на строках, различающихся символами, близкими к началу строки.

> то ухожу в монастырь

мужской? :)

> Код, чесно говоря, не совсем Microsoft`овский.

Не суть важно, можно говорить по данному коду, этот работает с ucs-2

> > Зато можно попробовать использовать RtlCompareMemory :
> )
>
> Но не нужно :), наверное.

Не нужно, для Юникод кодов менее $10000 ucs-2 совпадает с utf-16

> [46] clickmaker © (01.11.07 12:22)
> мужской? :)

Над этим вопросом еще не задумывалась.
А в какой нынче модно уходить ? :)

> [48] Anatoly Podgoretsky © (01.11.07 12:27)

> Не нужно, для Юникод кодов менее $10000 ucs-2 совпадает с utf-16

Ну и слава богу. Работы меньше :)

Из этой ветки я вынесла следующее:
Мне надо было имеющийся лист(массив) UNICODE_STRING`ов
обработать (сортировка, поиск дубликатв) и преобразовать в ANSI.
Вопрос был в следующем: что сначала преобразовать в Ansi или обрабатывать.
Если я правильно поняла, то обработка его в исходном виде лучше.
Ускорения при использовании Ansi мы не обнаружили, зато выяснили,
что многие Ansi функции работают через UNICODE.

За что всем большое спасибо :)

> зато выяснили,
> что многие Ansi функции работают через UNICODE.

Попутно можно выяснить, что Ansi функции могут не работать в общем случае, никогда нет гарантии в возможности преобразования Юникод в Ansi

> [50] Anatoly Podgoretsky © (01.11.07 23:15)
> Попутно можно выяснить, что Ansi функции могут не работать в общем случае,
> никогда нет гарантии в возможности преобразования Юникод в Ansi

Тоже очень полезное "выяснение" :)
P.S.
Похоже пора работать только в UNICODE - проблем меньше, "взаимопонимания" с системой больше :)

> Riply (02.11.2007 09:30:51) [51]

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

> [52] Anatoly Podgoretsky © (02.11.07 09:50)
> TNT Contros и не должного уровня и не покрывает все потребностей, хорошо хоть базовые покрывает.
> Я во всех проектах использую эту библиотеку в обязательном порядке.

"Чем дальше в лес - тем больше дров".
Впервые слышу об этой библиотеке. Где ее можно посмотреть и потрогать ?

> Riply (02.11.2007 10:28:53) [53]

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

> [54] Anatoly Podgoretsky © (02.11.07 10:35)
> Но если есть желание то могу выслать на твой почтовый ящик.

Желание есть. :) Буду очень признательна.

P.S.
Надеюсь моя анкета цела. Вроде надавно перерегистрироавлась.

Вот натолкнулась на функцию в WideStrUtils:

function WStrComp(const Str1, Str2: PWideChar): Integer; assembler; asm PUSH EDI PUSH ESI MOV EDI,EDX MOV ESI,EAX MOV ECX,0FFFFFFFFH XOR EAX,EAX REPNE SCASW NOT ECX NOT ECX MOV EDI,EDX XOR EDX,EDX REPE CMPSW MOV AX,[ESI-2] MOV DX,[EDI-2] SUB EAX,EDX POP ESI POP EDI end;

Она внутри использует что-то типа CompareMem или
"по идеологии" похожа на RtlCompareUnicodeString в [35] Riply © ?

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

> [57] guav © (02.11.07 21:43)
> Ищет нуль в конце одной из строк для определения длины, затем сравнивает по два байта.

Именно это меня и интересовало. Спасибо.
Т.е. использует "посимвольное" сравнение как и RtlCompareUnicodeString
и не пытается сравнивать по четыре байта ?

Сравни
> REPE CMPSD
> JNE @@2
> MOV ECX,EDX
> REPE CMPSB

и

> REPE CMPSW

посимвольно :)

Функция тоже использует вычитание символов, и в отличии от RtlCompareUnicodeString всегда использует такое вычитание (это работает т.к. #0 меньше любого символа)

Скорость сравнения строк в Ansi и Unicode формате. Найти похожие ветки