форумы  помощь  поиск  регистрация  майллист  ВХОД  слежка

Вариант для распечатки		Архивированная нить - только для чтения!  Пред. тема | След. тема
Форумы Программирование под UNIX (Public)
Изначальное сообщение		[Проследить за развитием треда]

"битовые операции, оптимизация работы со строками"
Сообщение от NL on 25-Сен-03, 12:43  (MSK)
есть простенькая задача: нужно все буквы в строке привести к нижнему регитсру. реализация до безобразия проста void func1(char *c_str, int len) { char *c_str_end; c_str_end = c_str + len; while(c_str < c_str_end){ *c_str++ |= 0x20; } } но я так понимаю, каждый раз процессору я подсовываю 8 бит (char) для обработки, хотя процессор способен за такт сделать операцию над 32 битами. не буду вдаваться в технические дебри и выяснять, как процессор использует  свободные биты и чем их заполняет. очевидно, что в данной задаче возможности процессора используются не полностью. Было бы лучше процессору подсовывать на обработку 32 бита (int). Для этого строку нужно преобразовать к int, и пробежать по елементам массива, накладывая соответствующую маску 0x20202020. Есть загвоздка, хорошо, если длина строки кратна 4 или sizeof(int). Но, если длина строки не кратна 4, то, накладывая маску, можно повредить данные за пределами вверенной мне области памяти. Поэтому, как не крути, оставшиеся байты придется перебрать в цикле как char и наложить соответствующую маску 0х20. вот реализация: void func2(char *c_str, int len) {     int *i_str, *i_str_end;     char *c_str_end;     i_str = (int*)c_str;     i_str_end = i_str + (int)(len/sizeof(int));     while(i_str<i_str_end){ *i_str++ |= 0x20202020;     }     c_str = (char*)i_str_end;     c_str_end = c_str + len%sizeof(int);     while(c_str<c_str_end){ *c_str++ |= 0x20;     } } Внимание вопрос: верны ли мои размышления, будет ли вторая функция работать быстрее, чем первая? при какой длине строки вторая функция будет работать быстрее ?
	Рекомендовать в FAQ | Cообщить модератору | Наверх

Индекс форумов | Темы | Пред. тема | След. тема

Сообщения по теме

1. "битовые операции, оптимизация работы со строками"
Сообщение от bsd on 25-Сен-03, 18:00  (MSK)
>есть простенькая задача: нужно все буквы в строке привести к нижнему регитсру. >реализация до безобразия проста > >void func1(char *c_str, int len) >{ >char *c_str_end; >c_str_end = c_str + len; >while(c_str < c_str_end){ >*c_str++ |= 0x20; >} >} > >но я так понимаю, каждый раз процессору я подсовываю 8 бит (char) >для обработки, хотя процессор способен за такт сделать операцию над 32 >битами. не буду вдаваться в технические дебри и выяснять, как процессор >использует  свободные биты и чем их заполняет. очевидно, что в >данной задаче возможности процессора используются не полностью. Было бы лучше процессору >подсовывать на обработку 32 бита (int). Для этого строку нужно преобразовать >к int, и пробежать по елементам массива, накладывая соответствующую маску 0x20202020. >Есть загвоздка, хорошо, если длина строки кратна 4 или sizeof(int). Но, >если длина строки не кратна 4, то, накладывая маску, можно повредить >данные за пределами вверенной мне области памяти. Поэтому, как не крути, >оставшиеся байты придется перебрать в цикле как char и наложить соответствующую >маску 0х20. вот реализация: > >void func2(char *c_str, int len) >{ >    int *i_str, *i_str_end; >    char *c_str_end; > >    i_str = (int*)c_str; >    i_str_end = i_str + (int)(len/sizeof(int)); >    while(i_str<i_str_end){ > *i_str++ |= 0x20202020; >    } >    c_str = (char*)i_str_end; >    c_str_end = c_str + len%sizeof(int); >    while(c_str<c_str_end){ > *c_str++ |= 0x20; >    } >} > >Внимание вопрос: верны ли мои размышления, будет ли вторая функция работать быстрее, >чем первая? при какой длине строки вторая функция будет работать быстрее > Пример плох! Нет смысла в данной реализации ! Отдай на откуп комппилятору оптимизацию кода!Используя приведение типов теряешь драгоценое время.
	Рекомендовать в FAQ | Cообщить модератору | Наверх

	2. "битовые операции, оптимизация работы со строками"
	Сообщение от NL on 25-Сен-03, 19:29  (MSK)
	>Пример плох! Нет смысла в данной реализации ! Отдай на откуп комппилятору >оптимизацию кода!Используя приведение типов теряешь драгоценое время. > там всего 2 приведения типов, первое когда указатель на строку привожу к int*, что бы потом можно было работать со всеq строкой как с массивом int, и второе приведение c_str = (char*)i_str_end; что бы вычислить адрес, откуда надо начинать преобразовавыть оставшиеся байты (которые не кратны 4) c_str_end = c_str + len%sizeof(int); все, больше нигде приведений типов нет. и особо много времени я не теряю. зато в первом цикле в 4 раза меньше прогонов, по сравнению с тем, если бы это был массив char. данная функция будет пириписываться на ассемблер, и отдавать здесь оптимизацию на откуп компилятору не разумно, да вообще надеяться на оптимизацию компилятором не стоит. и привел я эту функцию на сях, чтобы было наглядно видно все изменения есть еще какие-либо мнения по этому поводу ???
		Рекомендовать в FAQ | Cообщить модератору | Наверх

3. "битовые операции, оптимизация работы со строками"
Сообщение от vnp on 25-Сен-03, 22:37  (MSK)
>есть простенькая задача: нужно все буквы в строке привести к нижнему регитсру. >реализация до безобразия проста > >void func1(char *c_str, int len) >{ >char *c_str_end; >c_str_end = c_str + len; >while(c_str < c_str_end){ >*c_str++ |= 0x20; >} >} > >но я так понимаю, каждый раз процессору я подсовываю 8 бит (char) >для обработки, хотя процессор способен за такт сделать операцию над 32 >битами. не буду вдаваться в технические дебри и выяснять, как процессор >использует  свободные биты и чем их заполняет. очевидно, что в >данной задаче возможности процессора используются не полностью. Было бы лучше процессору >подсовывать на обработку 32 бита (int). Для этого строку нужно преобразовать >к int, и пробежать по елементам массива, накладывая соответствующую маску 0x20202020. >Есть загвоздка, хорошо, если длина строки кратна 4 или sizeof(int). Но, >если длина строки не кратна 4, то, накладывая маску, можно повредить >данные за пределами вверенной мне области памяти. Поэтому, как не крути, >оставшиеся байты придется перебрать в цикле как char и наложить соответствующую >маску 0х20. вот реализация: > >void func2(char *c_str, int len) >{ >    int *i_str, *i_str_end; >    char *c_str_end; > >    i_str = (int*)c_str; >    i_str_end = i_str + (int)(len/sizeof(int)); >    while(i_str<i_str_end){ > *i_str++ |= 0x20202020; >    } >    c_str = (char*)i_str_end; >    c_str_end = c_str + len%sizeof(int); >    while(c_str<c_str_end){ > *c_str++ |= 0x20; >    } >} > >Внимание вопрос: верны ли мои размышления, будет ли вторая функция работать быстрее, >чем первая? при какой длине строки вторая функция будет работать быстрее >? Sorry for English. Few things you have to keep in mind: 1. Is there a guarantee that a string is aligned to (int *)? If not, you must special case the beginning of the string as well. 2. Is there a guarantee that sizeof(int) is 4? If not, you must select a mask accordingly. 3. Is there a guarantee that a string consists exclusively of the letters? If not, you must test each character to avoid "lowercasing" digits, punctuation, spaces etc. 4. Is there a gurantee that a string is ASCII? Bottomline: tolower() was invented for the purpose. Do not reimplement a wheel.
	Рекомендовать в FAQ | Cообщить модератору | Наверх

	4. "битовые операции, оптимизация работы со строками"
	Сообщение от NL on 26-Сен-03, 11:43  (MSK)
	>Sorry for English. >Few things you have to keep in mind: >1. Is there a guarantee that a string is aligned to (int >*)? If not, you must special case the beginning of the >string as well. да, этот вариант мной предусмотрен. перед первым циклом я расчитываю сколько полных слов кратных sizeof(int) есть в строке (int)(len/sizeof(int)) далее расчитываю крайний адрес где эти слова заканчиваются i_str_end = i_str + (int)(len/sizeof(int)); т.е. я себя обезапасил от выхода за пределы строки если строка не кратна sizeof(int), то я расчитываю сколько байт остается за пределами i_str_end, другими словами сколько байт осталось необработанными len%sizeof(int) и потом расичитываю адреса в пределах которых лежат эти байты c_str = (char*)i_str_end c_str_end = c_str + len%sizeof(int) и пробегаю но ним в цикле >2. Is there a guarantee that sizeof(int) is 4? If not, you >must select a mask accordingly. вот тут мой промах. в таком случае маску можно вычислить например так int i,size,mask=0; size = sizeof(int); for(i=0; i<size; i++){ mask << i*8; mask += 0x20; } >3. Is there a guarantee that a string consists exclusively of the >letters? If not, you must test each character to avoid "lowercasing" >digits, punctuation, spaces etc. здесь я ничего противопоставить не могу, раз придется проверять каждый символ, то вся моя задумка никуда не годится, загребать сразу по 4 байта не получится :-( >4. Is there a gurantee that a string is ASCII? > да строки только ASCII >Bottomline: tolower() was invented for the purpose. Do not reimplement a wheel. > смысл понятен, моя прога будет применима только для строк ASCII состоящей только из букв. спасибо за замечания. Диагноз: прогу в утиль
		Рекомендовать в FAQ | Cообщить модератору | Наверх

	5. "битовые операции, оптимизация работы со строками"
	Сообщение от vnp on 26-Сен-03, 13:40  (MSK)
	>>Sorry for English. >>Few things you have to keep in mind: >>1. Is there a guarantee that a string is aligned to (int >>*)? If not, you must special case the beginning of the >>string as well. >да, этот вариант мной предусмотрен. перед первым циклом я расчитываю сколько полных >слов кратных sizeof(int) есть в строке (int)(len/sizeof(int)) >далее расчитываю крайний адрес где эти слова заканчиваются >i_str_end = i_str + (int)(len/sizeof(int)); >т.е. я себя обезапасил от выхода за пределы строки Я имел в виду не столько конец строки, сколько ее начало... В некоторых архитектурах (m68k, к примеру), невыровненный доступ приведет к bus error; в других (i386) --  к дикому замедлению.
		Рекомендовать в FAQ | Cообщить модератору | Наверх

	6. "битовые операции, оптимизация работы со строками"
	Сообщение от NL on 26-Сен-03, 14:20  (MSK)
	>Я имел в виду не столько конец строки, сколько ее начало... В >некоторых архитектурах (m68k, к примеру), невыровненный доступ приведет к bus error; >в других (i386) --  к дикому замедлению. ясно. нужно получше изучить аппаратную часть вопроса. тогда такой вопрос появился. есть число типа int  и мне нужно периодически делать какие то действия над его битами скажем 8-15 (второй байт слова). если я вычислю адрес этого второго байта и присвою указателю типа char, то будут операции над char* выполняться быстрее, чем над int* продемострирюу на примере int *a; for(...)*a |= 0x00ff0000; и работа с char int *a; char *c; c = (char*)a; c++; //смещаюсь на второй байт слова а for(...) *c |= 0xff; какой цикл будет работать быстрее, первый или второй. и вообще, стоит ли делать такие преобразования? речь идет об архитектуре х86.
		Рекомендовать в FAQ | Cообщить модератору | Наверх

	7. "битовые операции, оптимизация работы со строками"
	Сообщение от vnp on 26-Сен-03, 15:15  (MSK)
	>>Я имел в виду не столько конец строки, сколько ее начало... В >>некоторых архитектурах (m68k, к примеру), невыровненный доступ приведет к bus error; >>в других (i386) --  к дикому замедлению. > >ясно. нужно получше изучить аппаратную часть вопроса. >тогда такой вопрос появился. есть число типа int  и мне нужно >периодически делать какие то действия над его битами скажем 8-15 (второй >байт слова). >если я вычислю адрес этого второго байта и присвою указателю типа char, >то будут операции над char* выполняться быстрее, чем над int* >продемострирюу на примере >int *a; >for(...)*a |= 0x00ff0000; > >и работа с char >int *a; >char *c; >c = (char*)a; >c++; //смещаюсь на второй байт слова а >for(...) *c |= 0xff; > >какой цикл будет работать быстрее, первый или второй. и вообще, стоит ли >делать такие преобразования? речь идет об архитектуре х86. Что быстрее, честно говоря, не знаю. Если скорость -- вопрос жизни и смерти, то надо смотреть на генерируемый код (gcc -s), и считать циклы. Дело это нелегкое, т.к. нужно учитывать кеш и прочие превходящие. Опять-таки bottomline: компилятору - компиляторово. Код же должен быть (1) понятнын и (2) портируемым. Поэтому я бы предпочел 1-й вариант.
		Рекомендовать в FAQ | Cообщить модератору | Наверх

	8. "битовые операции, оптимизация работы со строками"
	Сообщение от NL on 26-Сен-03, 15:40  (MSK)
	>Что быстрее, честно говоря, не знаю. Если скорость -- вопрос жизни и >смерти, то надо смотреть на генерируемый код (gcc -s), и считать >циклы. Дело это нелегкое, т.к. нужно учитывать кеш и прочие превходящие. > > >Опять-таки bottomline: компилятору - компиляторово. Код же должен быть (1) понятнын и >(2) портируемым. Поэтому я бы предпочел 1-й вариант. дело в следующем. есть довольно большой проект на си, который уже работает и выдает результат. требуется этот проект довести до совершенства, т.е. максимально увеличить скорость работы. было принято решение часть функций переписать на ассемблере, вот у меня и появились такие вопросы по потимизации. в общем направления куда рыть определились.
		Рекомендовать в FAQ | Cообщить модератору | Наверх

	9. "битовые операции, оптимизация работы со строками"
	Сообщение от Мартовский заец on 26-Сен-03, 21:45  (MSK)
	>дело в следующем. есть довольно большой проект на си, который уже работает >и выдает результат. требуется этот проект довести до совершенства, т.е. максимально >увеличить скорость работы. было принято решение часть функций переписать на ассемблере, >вот у меня и появились такие вопросы по потимизации. в общем >направления куда рыть определились. Если не совсем опоздал:) В линухе есть профилер ПО, попробуй с его помощью поработать... А указанные тобой примеры много не дадут... Насчет операций с байтом или числом: в ДОС и винде компиляторы генерят по ОДНОЙ инструкции на арифметическое действие и в первом случае и во втором. Незнаю, как в линухах, но наверна также. Так что выигрыш во втором случае БУДЕТ! Но зависит от (1)частоты  вызова циклов; (2) - длины обрабатываемых массивов. Я такой метод оптимизации применял на 486 компах при работе с видеопамятью напрямую...
		Рекомендовать в FAQ | Cообщить модератору | Наверх

	10. "битовые операции, оптимизация работы со строками"
	Сообщение от NL on 29-Сен-03, 10:59  (MSK)
	>Если не совсем опоздал:) >В линухе есть профилер ПО, попробуй с его помощью поработать... >А указанные тобой примеры много не дадут... >Насчет операций с байтом или числом: в ДОС и винде компиляторы генерят >по ОДНОЙ инструкции на арифметическое действие и в первом случае и >во втором. Незнаю, как в линухах, но наверна также. >Так что выигрыш во втором случае БУДЕТ! >Но зависит от (1)частоты  вызова циклов; >(2) - длины обрабатываемых массивов. >Я такой метод оптимизации применял на 486 компах при работе с видеопамятью >напрямую... это понятно, что на одно арифм. действие генерится одна инструкция, но в последнем примере смысл такой: мне известно, что накладывать маску на все 4 байта не требуется, а достаточно только одного байта, и в принципе циклы будут работать с одинаковой скоростью (в обоих циклах одна и та же операция), но во втором случае я в проц. загоняю только 8 бит, и, на сколько мне хватает знаний, остальные 24 биты не будут простаивать, а будут заполненые данными из других процессов, таким образом, в своей конкретной задаче я не добьюсь реального прироста производительности, но скорость работы системы в целом увеличится. прошу вас это либо подтвердить либо опровергнуть и указать на мои ошибки
		Рекомендовать в FAQ | Cообщить модератору | Наверх

	11. "битовые операции, оптимизация работы со строками"
	Сообщение от Мартовский заец on 02-Окт-03, 08:49  (MSK)
	>это понятно, что на одно арифм. действие генерится одна инструкция, но в >последнем примере смысл такой: мне известно, что накладывать маску на все >4 байта не требуется, а достаточно только одного байта, и в >принципе циклы будут работать с одинаковой скоростью (в обоих циклах одна >и та же операция), но во втором случае я в проц. >загоняю только 8 %
		Рекомендовать в FAQ | Cообщить модератору | Наверх

	12. "битовые операции, оптимизация работы со строками"
	Сообщение от Мартовский заец on 02-Окт-03, 08:49  (MSK)
	>это понятно, что на одно арифм. действие генерится одна инструкция, но в >последнем примере смысл такой: мне известно, что накладывать маску на все >4 байта не требуется, а достаточно только одного байта, и в >принципе циклы будут работать с одинаковой скоростью (в обоих циклах одна >и та же операция), но во втором случае я в проц. >загоняю только 8 бит, и, на сколько мне хватает знаний, остальные >24 биты не будут простаивать, а будут заполненые данными из других >процессов, таким образом, в своей конкретной задаче я не добьюсь реального >прироста производительности, но скорость работы системы в целом увеличится. прошу вас >это либо подтвердить либо опровергнуть и указать на мои ошибки Насколько мне известно - нет! :) Будут использованы только 8 бит арифметики! Многопроцессность - это всего лишь ЧЕРЕДОВАНИЕ выполнения процессором команд из разных процессов! Не более!!! Выполныется несколько команд одного процесса, потом из другого и т.д... Так что, Забив в процессор 32!!! бита данных, ты сократишь количество циклов программы в 4 раза по сравнению с 8-ми битной арифметикой! На этом и основаны инструкции ММХ, SSE и т.д.... Они обрабатывают параллельно пачку байтов и уменьшают циклы обработки!
		Рекомендовать в FAQ | Cообщить модератору | Наверх

	13. "битовые операции, оптимизация работы со строками"
	Сообщение от Olej on 02-Окт-03, 17:44  (MSK)
	>Многопроцессность - это всего лишь ЧЕРЕДОВАНИЕ выполнения процессором команд из разных процессов! >Не более!!! Выполныется несколько команд одного процесса, потом из другого и >т.д... Вот здесь позвольте не согласиться - не из процессов, а из [b]потоков[/b] - это на сегодня оформлено и в требованиях POSIX, и может приводить к существенно отличающимся последствиям. >Так что, Забив в процессор 32!!! бита данных, ты сократишь количество циклов >программы в 4 раза по сравнению с 8-ми битной арифметикой! >На этом и основаны инструкции ММХ, SSE и т.д.... Они обрабатывают параллельно >пачку байтов и уменьшают циклы обработки! А вот относительно "ММХ, SSE" если это из С/С++ кода - то крайне осторожно - это принципиально зависит от конкретной OS, используемого в ней компилятора, и его версии... Насколько я в курсе (может и нет :-)) - gcc даже свежих используемых версий - не использует SSE.
		Рекомендовать в FAQ | Cообщить модератору | Наверх

	14. "битовые операции, оптимизация работы со строками"
	Сообщение от Мартовский заец on 04-Окт-03, 11:10  (MSK)
	>>Многопроцессность - это всего лишь ЧЕРЕДОВАНИЕ выполнения процессором команд из разных процессов! >>Не более!!! Выполныется несколько команд одного процесса, потом из другого и >>т.д... >Вот здесь позвольте не согласиться - не из процессов, а из [b]потоков[/b] >- это на сегодня оформлено и в требованиях POSIX, и может >приводить к существенно отличающимся последствиям. > Ок, сознаю свою ошибку:) Терины перепутал, но общая мысля остается верной!!! >>Так что, Забив в процессор 32!!! бита данных, ты сократишь количество циклов >>программы в 4 раза по сравнению с 8-ми битной арифметикой! >>На этом и основаны инструкции ММХ, SSE и т.д.... Они обрабатывают параллельно >>пачку байтов и уменьшают циклы обработки! >А вот относительно "ММХ, SSE" если это из С/С++ кода - то >крайне осторожно - это принципиально зависит от конкретной OS, используемого в >ней компилятора, и его версии... Насколько я в курсе (может и >нет :-)) - gcc даже свежих используемых версий - не использует >SSE. > А вот тут никто про С/С++ и тем более про gcc не упоминал:) Я просто привел пример ускорения обработки данных засчет распаралеливания некоторых операций:) В ДОСе и винде все делается просто и качественно:) Насчет линуха - нивкурсах!
		Рекомендовать в FAQ | Cообщить модератору | Наверх

	15. "битовые операции, оптимизация работы со строками"
	Сообщение от Макс Зиналь on 04-Окт-03, 22:23  (MSK)
	>ней компилятора, и его версии... Насколько я в курсе (может и >нет :-)) - gcc даже свежих используемых версий - не использует >SSE. Вроде бы умеет, и даже SSE2. Однако результирующий код выполняется только на камушках, оный SSE2 поддерживающих. Так что режим не совсем стандартный.
		Рекомендовать в FAQ | Cообщить модератору | Наверх

Удалить

Индекс форумов | Темы | Пред. тема | След. тема

Пожалуйста, прежде чем написать сообщение, ознакомьтесь с данными рекомендациями.