Скорость сравнения строк в 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 ?

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

Не ты первая.

> 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 вообще маньяки !!!

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

где ?

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

> [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 вообще маньяки !!!

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

> [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; }

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

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

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

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

:)

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

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

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

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

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

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

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