Вадим Никулин wrote:
> Здравствуйте, MaximE, Вы писали: > >>> 1) Сложность алгоритма считается в наихудшем и асимптотическая ( в O()). >>> 2) Размер P-массива равен n — и n может (считаем поведение на бесконечности) быть оЧень большим > > ME>memset не работает на бесконечности > > Приколы приколами, а все же. Внутри все-равно цикл есть. Все-равно количество тактов процессора, которое тратится на выполнение memset, зависит от размера массива линейно.
Ok. Пусть количество итераций алгоритма i(n), сложность O(f(n)). Сложность memset на 32-битной платформе m(n) = c * n / 4. Добавление memset в каждую итерацию сделает O() алгоритма O(f(n) + i(n) * m(n)), т.е. не переводит алгоритм в (общую) группу с более высокой сложностью.
А смысл?
Представь себе, что какой-то указатель случайно принял валидное значение. Проверка удачно прошла, ты этим значением воспользовался... а потом будешь ловить совершенно непредсказуемые логические ошибки.
Следовательно, ты не должен им воспользоваться. То есть, у тебя имеется какой-то ещё критерий, вытекающий из логики программы, — валидный указатель или нет. Нужно ли брать его значение или не нужно. Обращаться к этому элементу массива указателей или к другому.
А если такой критерий есть, то зачем все эти хитрости с проверками?
Здравствуйте, Вадим Никулин, Вы писали:
ВН>Здравствуйте, LaptevVV, Вы писали:
F>>>Что-то не похоже на константу? (n — большое) LVV>>Там цепочечная команда работает... До 256к на интеле одной командой...
ВН>А вот хотелось бы поразвернутее услышать про это чудо. Вы утверждаете, что 256к и 100 байтов обнуляются одно и то же (константное) время?
Не, разница, конечно есть, но лишних выполняемых в цикле команд нет... ВН>И, кстати, даже если 256к за одну команду, то для N байтов нужно N/256К команд, что, очевидно, есть O(N).
Это ж команда stosd
ей же "до лампочки", сколько двойных слов за раз — пропиши счетчик в cx, а в ES:DI — адрес начала... Хотя сейчас можно и ЕСХ использовать...
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Т.е. они помогут выловить, является ли значение в массиве P[i] вообще указателем куда-либо или нет.
Т.е. эти функции стоит применять до того, как делать вообще какие-либо сравнения, и они ( в частности) могут помочь избежать причины вызова одного типа exception ( что это вообще не поинтер).
Останется только 2) Словить эксепшн если валидный указатель, но не допускает сравнения 3) и сравнивать ?
Кстати, эти функции хоть нормально работают: что-то annoy и еще встречал
flax wrote:
> ME>Именно так. memset не увеличит количество итераций твоего алгоритма, лишь сделает каждую итерацию медленнее, поэтому memset не сделает из O(n * log(n)) алгоритма O(n^2) алгоритм. > > Можно подробнее... что-то я запутался. > 1) Если мы говорим о O(n), то вообще говоря рассмативаем поведение lim > Т.е. фразу "время работы функции не константа, но сложность общего алгоритма использование этой функции не увеличит" я не понимаю. Я могу понять, что если функция не константа, то она ( в любом случае) увеличит сложность алгорима, другое дело, что O(n^2) равно O(n^2 + log(n)) по принципам сложения этих асимптотик. > > Итак, если функция (вообще говоря) не константа, тогда сразу же хочется узнать какова ее сложность. Вполне возможно, что порядок ее роста может быть ассимптотически малым, что-то похожее на [ O(F(n)) "почти линейные",Ахо], т.е.почти еще какие-либо...Но в любом случае сложность O(какая-то оценка от n), если она не константа, должна быть.
Я именно и имел ввиду, что, скорее всего, сложность memset асимптоматически мала относительно сложности всего цикла алгоритма, поэтому сложностью memset можно принебречь.
> 2) Если я правильно понял Lapteva, то реализация этой функции зашита в Intel-процессоры и способна (так же как мы считаем cкорость выполнения адресации в RandomAccessMemory к произвольному элементу за O(1)) на масштабах до 256к делать зануление последовательного куска памяти за O(1).
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, flax, Вы писали:
К><>
К>А смысл?
ок
К>Представь себе, что какой-то указатель случайно принял валидное значение. Проверка удачно прошла, ты этим значением воспользовался... а потом будешь ловить совершенно непредсказуемые логические ошибки.
К>Следовательно, ты не должен им воспользоваться. То есть, у тебя имеется какой-то ещё критерий, вытекающий из логики программы, — валидный указатель или нет.Нужно ли брать его значение или не нужно. Обращаться к этому элементу массива указателей или к другому.
да.
Должен узнать, содержит ли массив А данное число или нет. Иду (как по хешу) в i-й элемент P, там либо указатель невесть_куда ( вот собственно о нем и вопрос), либо в массив A.
Если в А, перехожу в массив A на это число, если это число = i (т.е. то, что спрашивал), значит i содержится в А, что я собственно и хотел узнать. Если это число не i, то значит был обман, так как я заранее поставил в P все указатели на элементы А.
К>А если такой критерий есть, то зачем все эти хитрости с проверками?
Понятно теперь зачем?
@ (на меня + что-то близкое Ахо, Хопкрофт, Ульман "Анализ и ..." (глава 2 упражнения ***))
Здравствуйте, LaptevVV, Вы писали:
ВН>>И, кстати, даже если 256к за одну команду, то для N байтов нужно N/256К команд, что, очевидно, есть O(N).
LVV>Это ж команда stosd LVV>ей же "до лампочки", сколько двойных слов за раз — пропиши счетчик в cx, а в ES:DI — адрес начала... Хотя сейчас можно и ЕСХ использовать...
Cпросил тех кто знает, правда ли — говорят "правда можно, и упоминают о предсказании размера блока процессора".
Если это возможно, расскажите подробнее (для тех кто ASM не знает).
Весьма интересно, и, честно говоря, выглядит пока что-то из разряда "чудеса и мистификации"
Hello, flax!
You wrote on Mon, 06 Dec 2004 10:12:50 GMT:
SDB>> Фунукции IsBad*Ptr() не подойдут?
f> Т.е. они помогут выловить, является ли значение в массиве P[i] вообще f> указателем куда-либо или нет.
Они говорят ровно об одном — будет ли AV при записи/чтении по данному
адресу.
f> Т.е. эти функции стоит применять до того, как делать вообще какие-либо f> сравнения, и они ( в частности) могут помочь избежать причины вызова f> одного типа exception ( что это вообще не поинтер).
f> Останется только 2) Словить эксепшн если валидный указатель, но не f> допускает сравнения 3) и сравнивать ?
f> Кстати, эти функции хоть нормально работают: f> [url=http://www.ostalk.org/prevent_assert_in_IsBadReadWriteCodePtr___-90 f> 26533-5466-a.html]что-то annoy[/url] и еще встречал
Нулями пробить будет гораздо быстрее, чем с IsBad*Ptr маятся
With best regards, Sergey.
Posted via RSDN NNTP Server 1.9 delta
Одним из 33 полных кавалеров ордена "За заслуги перед Отечеством" является Геннадий Хазанов.
Здравствуйте, flax, Вы писали:
F>Должен узнать, содержит ли массив А данное число или нет. Иду (как по хешу) в i-й элемент P, там либо указатель невесть_куда ( вот собственно о нем и вопрос), либо в массив A.
F>Если в А, перехожу в массив A на это число, если это число = i (т.е. то, что спрашивал), значит i содержится в А, что я собственно и хотел узнать. Если это число не i, то значит был обман, так как я заранее поставил в P все указатели на элементы А.
Окей, но тогда зачем указатели? Нужно вместо них использовать индексы
Здравствуйте, LaptevVV, Вы писали:
LVV>Здравствуйте, Вадим Никулин, Вы писали:
ВН>>Здравствуйте, LaptevVV, Вы писали:
F>>>>Что-то не похоже на константу? (n — большое) LVV>>>Там цепочечная команда работает... До 256к на интеле одной командой...
ВН>>А вот хотелось бы поразвернутее услышать про это чудо. Вы утверждаете, что 256к и 100 байтов обнуляются одно и то же (константное) время? LVV>Не, разница, конечно есть, но лишних выполняемых в цикле команд нет... ВН>>И, кстати, даже если 256к за одну команду, то для N байтов нужно N/256К команд, что, очевидно, есть O(N). LVV>Это ж команда stosd LVV>ей же "до лампочки", сколько двойных слов за раз — пропиши счетчик в cx, а в ES:DI — адрес начала... Хотя сейчас можно и ЕСХ использовать...
Можно написать свою memset и она будет работать быстрее stosd.
Идею я прочитал у Криса Касперски. Идея в том, что пока обрабатывается текущий блок, находящийся в кэше нужно обратится к следующему блоку размером в этот самый кэш.
К тому времени, когда очередь дойдет до зануления памяти следующего блока он уже будет в кэше.
Крис приводит цифры, показывающие разное улучшение (по-моему до 25%) для разных процессоров.
Здравствуйте, MaximE, Вы писали:
ME>Я именно и имел ввиду, что, скорее всего, сложность memset асимптоматически мала относительно сложности всего цикла алгоритма, поэтому сложностью memset можно принебречь.
эхъ, но ведь когда пишут что моя library делает что-то -- указаывают ее реальную трудоемкость. И уже пользователь решает, велик или мал вклад этой библиотеки в общую асимптотическую сложность ЕГО алгоритма. А так, как говорите, получается вроде "lib у нас быстрая, а у тебя, x@№%"@@"№"!xx, все равно руки кривые, поэтому...можете считать, что сложностью нашей lib можете принебречь. Да, кстати, и размеры задач у вас маленькие".
Плохо так говорить.
>> 2) Если я правильно понял Lapteva, то реализация этой функции зашита в Intel-процессоры и способна (так же как мы считаем cкорость выполнения адресации в RandomAccessMemory к произвольному элементу за O(1)) на масштабах до 256к делать зануление последовательного куска памяти за O(1).
ME>Ты понял правильно, но он ошибается.
Да вот уже прямо рассказали, что даже от N обнуление не зависит...
итак
"Точная формулировка о memset"
На процессорах Intel можно обнулить последовательных N байт памяти за O(1)
Замечание/тест: массив[N=2 гига оперативки]. Вот мне отчего-то верится, что к предпоследнему байту (массив[n-1]) можно обратиться быстро, а вот выполнить memset (0,p_start,N) будет проблематичным.
На уровне интуиции, которая наверное уже врет..
"Вопрос о NonComparable"
Память NONcomparable. Т.е. на памяти введен лишь частичный порядок. Это сделано для того, чтобы менеджер памяти мог без головной боли перехать с одной машины на кластер
Так?
"Вопрос о памяти"
Доступ к памяти по индексу выполняется за O(1). Почему (это на уровне контроллера или просто _удобно считать_ что за O(1), и RAM — абстракция). Если это действительно так, что еще (вот говорят memset) можно выполнить за O(1)//ведь из того, что доступ по индексу за O(1) не следует что memset будет работать за O(1).
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, flax, Вы писали:
К>>>Окей, но тогда зачем указатели? Нужно вместо них использовать индексы
F>>Какие-такие индексы....
К>Индексы элементов массива A.
!!
Только тогда есть риск схватить что-то страшное при int x = P[i]:
и надо иметь функцию Is_этавещь_Int() или просто ждать exception.
flax wrote:
> Здравствуйте, MaximE, Вы писали: > > ME>Я именно и имел ввиду, что, скорее всего, сложность memset асимптоматически мала относительно сложности всего цикла алгоритма, поэтому сложностью memset можно принебречь. > > эхъ, но ведь когда пишут что моя library делает что-то -- указаывают ее реальную трудоемкость. И уже пользователь решает, велик или мал вклад этой библиотеки в общую асимптотическую сложность ЕГО алгоритма. А так, как говорите, получается вроде "lib у нас быстрая, а у тебя, x@№%"@@"№"!xx, все равно руки кривые, поэтому...можете считать, что сложностью нашей lib можете принебречь. Да, кстати, и размеры задач у вас маленькие". > > Плохо так говорить.
O-нотация служит для того, чтобы классифицировать алгоритмы по сложности (common orders of functions) и показать как она зависит от кол-ва элементов, но никак не для того, чтобы дать точные цифры производительности. Как, к примеру, ты учтешь в O-нотации скорость сравнения, копирования элементов, или swapping операционной системы?
Здравствуйте, MaximE, Вы писали:
ME>LaptevVV wrote:
ME>[]
>> Там цепочечная команда рабьотает... До 256к на интеле одной командой...
ME>Но эта команда реально выполняет цикл.
но без лишних КОМАНД цикла
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, MaximE, Вы писали:
ME>flax wrote:
ME>O-нотация служит для того, чтобы классифицировать алгоритмы по сложности (common orders of functions) и показать как она зависит от кол-ва элементов, но никак не для того, чтобы дать точные цифры производительности. Как, к примеру, ты учтешь в O-нотации скорость сравнения, копирования элементов, или swapping операционной системы?
Да. Все верно и согласен на все 100%. Меряю только сложность (не производительность), однако в RAM доступ к памяти по индексу O(1), а тут вдруг говорите, что обнулить массив O(1). Это меня и смущает, до сих пор.
Диллема, либо RAM (математическая) > Intel, т.е. абстракция O(1) не бывает, итд, поэтому также как доступ на самом деле зависит от значения индекса, так и memset тоже зависит, чуть в большей степени — но этого нет в RAM и все тут.
Либо RAM (математическая) < Intel (Intel extension for RAM) и мы можем считать, что как доступ O(1), так и зануление произвольного??? куска памяти O(1)
ME>-- ME>Maxim Yegorushkin
LaptevVV wrote:
> Здравствуйте, MaximE, Вы писали: > > ME>LaptevVV wrote: > > ME>[] > >>> Там цепочечная команда рабьотает... До 256к на интеле одной командой... > > ME>Но эта команда реально выполняет цикл. > но без лишних КОМАНД цикла
Вообще, rep stosd/movsd не эффективны, и в оптимизированных реализациях memset/memcpy заменены "лишними" командами цикла. Неэффективность становится заметной на массивах более 256-512 байт, поэтому на небольших массивах компиляторы вставляют intrinsic memset == rep stosd.
Причина неэффективности всех строковых операций в том, что они напрягают memory controller процессора лишь периодическими burst read/write, простаивая на загрузках кэша, в то время как цикл с "лишними" командами постоянно напрягает memory controller, позволяя достичь максимальной практической скорости заполнения/копирования.
F>"Вопрос о NonComparable"
F>Память NONcomparable. Т.е. на памяти введен лишь частичный порядок. Это сделано для того, чтобы менеджер памяти мог без головной боли перехать с одной машины на кластер
F>Так?
Я же не утверждаю ничего . Мне просто помнится (?!) что нейкий гуру, писал об этом. И у меня есть подозрения, что это был или Мейерс, или Элджер...
Перекуём баги на фичи!
Можно подробнее... что-то я запутался.
!! 
. Мне просто помнится (?!) что нейкий гуру, писал об этом. И у меня есть подозрения, что это был или Мейерс, или Элджер... 