Igor Korolyov
Ну и да, как тупая идея - распараллеливание задачи. Порезать строку на 4 части, отправить 4 (или больше, смотря сколько ядер в наличии) "схлопывающим" потоками, потом уж результаты сцепить. Вполне возможно что на гигабайтных данных это себя многократно оправдает

Возможно, но не факт. Задача исключительно на работу с памятью, а не на вычисления, а кэш нифига не резиновый, поэтому ядра будут постоянно конкурировать за доступ к памяти. Хотя из-за наличия небольшого L1 кэша данных у каждого ядра, скорей всего многопоточная обработка даст изрядный выигрыш.

spinz

Taran
А вот городить вставку на ассемблере без анализа потерь на каждую окружающую операцию я бы не стал.

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

Да согласен я. Еще более был бы согласен еслиб ожидалось в коце нечто

операция	fox	foxtools	asm	c.dll
read
alltrim
delspaces
save
%

Но ведь этого не будет.

spinz
Так оно, однако тем не менее интеловцы запилили команду PREFETCHx именно для упреждающего чтения в кэш.

Полагаю что это используется если профилировщик показывает неэффективную работу самого камня по упреждающему чтению, а не "я так думаю что стоит впихнуть". И как раз "я так думаю" что камень отлично справится с упреждающим чтением последовательных адресов памяти - это для сложных нелинейных структур может потребоваться "подсказывать" ему что "нет, мы не подряд тихо-мирно 100кб будем читать, мы будем по 1 байтику из каждого 1 Мб адресного пространства просматривать"... Но это чисто мои спекуляции "на тему", я не в курсе как работает логика префетча - в частности видел что она хорошо справляется и с "обратным" чтением - т.е. при декременте адресов. Вот для "истинного рандома" беда, по сути она не работает... Боюсь что там и явные подсказки не помогут...

Taran
Про foxtools речи нет. Речь о чистом фоксе.

А собственно говоря почему? Это вполне себе фоксовое решение - в отличии от ассемблерных вставок, активиксов и даже DECLARE-DLL. Расширение языка своими эффективными функциями (эффективными не в последнюю степень по причине доступа к внутренностям фокса - к переменных и полям, к его менеджеру памяти). При том доступное (конечно же в несколько ином виде) даже в FPD
Просто вырисовывается странная аналогия - мы начинаем сравнивать скорость телеги запряжённой парой лошадей, и кареты запряжённой, скажем, четвёркой. При том что рядом стоит тривиальная и банальная лада-калина "делающая" по скорости все эти повозки в РАЗЫ, заправленная и с ключами в замке - но нет, "это не средство передвижения, только навозовыделяющие двигатели есть труъ"

Taran
А вот городить вставку на ассемблере без анализа потерь на каждую окружающую операцию я бы не стал.

Согласен - потому я и говорю о том что замерять скорость надо "снаружи" - включая всю абсолютно необходимую для работы "обвязку". Ну да, можно убрать собственно время на "создание" подобной функции - т.к. это делается 1 раз, а потом вызывается хоть миллион. Но вот сам вызов, создание дополнительных буферов, их передачу/приём - это никак нельзя выкидывать из измерения...

Taran
Какова ожидаемая доля экономии при вставке маш.кодов?
И.... цена сопровождения.

Да очень приличная экономия - в разы как минимум. А цена сопровождения - вопрос другой. Ты же не знаешь как на сях написана собственно функция STRTRAN - просто её используешь. Так и тут - если есть корректно работающая функция в fll или в том же ассемблерном-байт-коде, то зачем её ещё как то "сопровождать"?
А чтобы она была корректной - ну как и веде - пишутся тесты со всякими "странными и маловероятными" граничными условиями - от пустой строки, и строки из одних пробелов до 1-символьных и Гигабайтноразмерных строк... Кстати, ровно такие же тесты можно прогонять и для всех прочих реализаций - результат то должен быть идентичным

spinz
Задача исключительно на работу с памятью, а не на вычисления, а кэш нифига не резиновый, поэтому ядра будут постоянно конкурировать за доступ к памяти. Хотя из-за наличия небольшого L1 кэша данных у каждого ядра, скорей всего многопоточная обработка даст изрядный выигрыш.

От размеров обрабатываемой строки зависит. Если там будет 1Гб, то уже ни разу не в кэш, и даже, возможно, не в RAM нагрузка задачи будет упираться...
Кроме того, для реальной системы с кучей исполняющихся задач критерием эффективности может быть не собственно "чистое время" выполнения, а ещё и использованные для этого общие ресурсы системы. Держать весь объём обрабатываемых "гигантских" данных в памяти - в 99% случаев не есть эффективно и правильно. Особенно если задача заключается в ОДНОМ ПРОХОДЕ по этим самым данным... Представь теперь что эту задачу выполняет сервер, которому на обработку поступают все тексты из Библиотеки Конгресса США. И насколько лучше будет запускать, к примеру, 10-20 параллельных процессов, по частям обрабатывающих гигабайтные массивы данных, в "скромном" 100-200Мб PrivateWorkingSet, нежели всего 2-3 процесса, каждый из которых сожрёт по 2 Гб памяти, исчерпав её полностью...

Taran
Но ведь этого не будет.

Why not?
Вона спинц соизволил сваять свой вариант на машкоде, всяких разных strtran-ов накидали прилично (хотя кроме самого первого с циклом, я бы сказал что корректных нет).
Сам reduce из foxtools подключить это 2 строки кода. Вот с тем чтобы нарисовать свою "специфическую" fll-функцию есть проблемы... Не уверен что в современных студиях нормально скомпилируется код с фоксовыми lib-ами...
Тесты разнообразные подогнать - тоже не большая проблема

Ну окей. Насчет foxtools я погорячился.
Давненько не использовал за ненадобностью.

Насчет обьявления функций и расходов на это. Насколько вижу маш.коды и обвязка срабатывать будут при каждом вызове.
Несколько это напрягает.
Т.е. задача именно для редкого вызова и большого текста. В каждый контрол на форме вставлять нет желания.
Вот ежели и делать, то мне кажется лучше все-таки внешнюю компоненту.
То что идея со вставкой интересная не отрицаю. Но... не, я не буду.
По крайней мере пока не попалась под это конкретная задача.

Ну это так на быструю руку накидали. Для работы все alloc да саму строку с машкодами достаточно 1 раз сделать, потом останется только вызов CallWindowProc, ну и подготовка буфера для него (хотя я бы его убрал - в саму "передаваемую строку" и помещал результат).
В "контрол на форме" вставляется в любом случае тривиальное Reduce(This.Value), как оно там внутри работает - не контрола забота

Ээх, заинтриговал красноречивый.
Что-то как-то я по жизни пропустил эту вашу reduce.
Хочу цифру. Две.

Taran
Хочу цифру. Две.

Луше бабу. Две.

Хотя, учитывая возраст, две может и многовато

Как и ожидалось, добавление prefetch'a выигрыша не дало, но проверить стоило.

Видимо, надо копать в сторону не процессорной оптимизации, а алгоритмической.

Но, хоть убей, не могу придумать как красиво парсить строку двордами и не потерять пробелы на границах соседних двордов

Дурацкая идея - за несколько проходов, например:
- начиная с байта №0 проходим по строке, удаляем DWORDы = 0h2020
- начиная с байта №1 делаем тоже самое

Вопросы:
...хз, смещение начального адреса на 1 не портит картину чтения DWORD-ами?
...двух этих проходов достаточно?

Доб. О! можно в файл записывать результат первого прохода, но не с 0-смещения, а с 1.
А что дает чтение DWORD-ами, а не байтами? проц все равно прочитает сразу пачку байтов, с запасом, наверное...

блин перепутал DWORD с WORD. Ну, идея все равно остается...



Исправлено 2 раз(а). Последнее : of63, 14.01.18 18:21

of63
А что дает чтение DWORD-ами, а не байтами? проц все равно прочитает сразу пачку байтов, с запасом, наверное...

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

время измерял с помощью HPET на строке
_test = Replicate("1",15000000)

шестерка
[attachment 28838 CaptureVfp9.PNG]

девятка
[attachment 28837 CaptureVfp6.PNG]

Шестерка рулит!



Исправлено 1 раз(а). Последнее : _vit, 14.01.18 22:47

Возможно, хотя я что-то несколько сомневаюсь в этом, что в 6-ке при вызове внешней функции ей отдавался непосредственно указатель на байтики строки (предварительно залоченный mhandle, чтобы сборщик мусора его не переместил), а не копия. Для теста я бы сравнил время работы "полезного" кода с пустым ret10 и всё. Это даст по сути время работы фоксового механизма вызова "внешней" функции - накладные расходы на вызов. Конечно же с той самой мега-строкой.
библиотечный reduce заведомо "сложнее" данной ассемблерной реализации - он помимо устранения дублирующихся пробелов ещё и как CHRTRAN(...,"abc"," ") работает - заменяет указанные символы на пробелы. Полагаю что он всё это за один проход делает, хотя как знать...

не, для сравнения ассемблерной реализации рулит RDTSC

Ребята, вам черепа не жмут?

тов.лулгу, вам бы не стоит пытаться играть в одной песочнице со старшими пацанами.

ваш уровень немного ниже, вот и оставайтесь на нем

2_vit
> время измерял с помощью HPET на строке
_test = Replicate("1",15000000)

Времена то порядка 0.1 сек, тут ОС наверное свое привносит. А если увеличить строку на порядок с 15М до 300М (или до предела, чтобы фокс не повесился), например, то какие будут времена?

of63
Времена то порядка 0.1 сек, тут ОС наверное свое привносит.

Он же даже специально распечатал "точность" HPET таймера В его конкретном случае точность таймера составляет 0.3 МИКРОсекунды.
ОС, конечно же, влияет. Идёт переключение на другие процессы в частности. Только зачем измерять сферического коня в вакууме - именно в условиях приближенных к реальным и следует проводить измерения. Вполне достаточно обеспечить работу измеряемой программы в Foreground режиме (не переключаться с ней на другие на время теста). При этом все реализации/алгоритмы будут находится в одинаковых условиях - а нам как раз важно относительное соотношение скоростей между ними, а не абсолютное значение.

of63
А если увеличить строку на порядок с 15М до 300М (или до предела, чтобы фокс не повесился), например, то какие будут времена?

Заодно и с очень короткими строками - вплоть до "пустой" - чтобы определить влияние "инфраструктуры" такого рода вызовов

spinz
для сравнения ассемблерной реализации рулит RDTSC

У него есть свои недостатки. Кроме того я ещё раз повторяю - в этой задаче критически важно измерять ВЕСЬ процесс - начиная от передачи параметров и заканчивая получением обратно в фоксе готового значения. Учитывая что там ещё и LEFT потребуется делать, чтобы "лишнюю" часть буфера отрезать (для fll не потребуется - она сама сможет это реализовать через _SetHandSize).

В общем потестил я разные варианты.

Самый вроде бы приемлемый, который не проседает в "граничных" случаях (одни пробелы, одни не-пробелы, очень короткие и очень длинные последовательности тех и других) - читать побайтово, а результат после анализа на пробел складывать в дворд и потом уже в буфер писать дворды. Если читать тоже двордами, то за счет усложнения логики, скорость падает.

Примерный код основного цикла

Что-то мне кажется что ты про запись последнего слова забыл (выход из внешнего цикла на _Label_4 независимо от пустоты/непустоты ebx) - если размер итоговой строки не будет кратен 4-м.