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, позволяя достичь максимальной практической скорости заполнения/копирования.
Здравствуйте, 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%) для разных процессоров.
Здравствуйте, flax, Вы писали:
F>С одной стороны, вроде можно, обставив проверку exception-ом ( на нем будут выявляться те указатели, которые вообще указывают неизвестно куда).
F>С другой стороны, где-то слышал, что память вроде как не comparable.
Фунукции IsBad*Ptr() не подойдут?
[ posted via RSDN@Home 1.1.4 beta 3 r241, accompanied by Metallica — And Justice For All ]
Здравствуйте, flax, Вы писали:
F>Здравствуйте, MaximE, Вы писали:
ME>>А что, занулить массив P указателей перед использованием нельзя? Потом сравнивай указатели с нулем, в чем проблема?
F>Занулять нельзя... тут вопросы с временной сложностью (иначе на каждом шаге n — зануляешь и n^2 -вылезет на всем алгоритме)
Гм. А что Вам мешает обнулить массив 1 вызовом функции memset?
flax wrote:
> ME>Ты меня не понял. Сложность зануления массива — c (memset), сложность зануления массива n раз — с * n. > > I як, братцы, это (за константу) реализовать??? > > >
Это действительно не константа, но ее время исполнения можно принять за константу, так как на каждой итерации он будет выполняться за константное время (если, конечно, размер твоего массива постоянен). Только если время выполнения memset будет равно времени исполнения одной итерации (что, как мне кажется, маловероятно), memset сможет повысить степень выражения асимптоматической сложности алгоритма.
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 wrote:
> Здравствуйте, MaximE, Вы писали: > > ME>Я именно и имел ввиду, что, скорее всего, сложность memset асимптоматически мала относительно сложности всего цикла алгоритма, поэтому сложностью memset можно принебречь. > > эхъ, но ведь когда пишут что моя library делает что-то -- указаывают ее реальную трудоемкость. И уже пользователь решает, велик или мал вклад этой библиотеки в общую асимптотическую сложность ЕГО алгоритма. А так, как говорите, получается вроде "lib у нас быстрая, а у тебя, x@№%"@@"№"!xx, все равно руки кривые, поэтому...можете считать, что сложностью нашей lib можете принебречь. Да, кстати, и размеры задач у вас маленькие". > > Плохо так говорить.
O-нотация служит для того, чтобы классифицировать алгоритмы по сложности (common orders of functions) и показать как она зависит от кол-ва элементов, но никак не для того, чтобы дать точные цифры производительности. Как, к примеру, ты учтешь в O-нотации скорость сравнения, копирования элементов, или swapping операционной системы?
Есть некоторый массив P указателей на int. В некоторые ячейки массива P были внесены указатели на элементы массива A (int), однако валидные значения были внесены не во все элементы P, и в некоторых ячейках массива P находятся неинициализированные, случайные значения ( то, что было на этом месте в памяти)
Можно ли, взяв произвольный указатель x из P (x = P[i]), проверить указывает ли он на (какой-либо) элемент
массива (т.е. проверить указывает ли он в интервал памяти &a[0], &a[n-1]).
С одной стороны, вроде можно, обставив проверку exception-ом ( на нем будут выявляться те указатели, которые вообще указывают неизвестно куда).
С другой стороны, где-то слышал, что память вроде как не comparable.
flax wrote:
> Есть некоторый массив P указателей на int. В некоторые ячейки массива P были внесены указатели на элементы массива A (int), однако валидные значения были внесены не во все элементы P, и в некоторых ячейках массива P находятся неинициализированные, случайные значения ( то, что было на этом месте в памяти)
А что, занулить массив P указателей перед использованием нельзя? Потом сравнивай указатели с нулем, в чем проблема?
Здравствуйте, flax, Вы писали:
F>Можно ли, взяв произвольный указатель x из P (x = P[i]), проверить указывает ли он на (какой-либо) элемент F>массива (т.е. проверить указывает ли он в интервал памяти &a[0], &a[n-1]).
flax wrote:
> Здравствуйте, MaximE, Вы писали: > > > ME>А что, занулить массив P указателей перед использованием нельзя? Потом сравнивай указатели с нулем, в чем проблема? > > Занулять нельзя... тут вопросы с временной сложностью (иначе на каждом шаге n — зануляешь и n^2 -вылезет на всем алгоритме)
Сложность зануления можно принять как c * n, где с — константа. Тогда сложность будет O(x + c * n), т.е. зануление не должно оказать значительного влияния.
Здравствуйте, MaximE, Вы писали:
>> >> Занулять нельзя... тут вопросы с временной сложностью (иначе на каждом шаге n — зануляешь и n^2 -вылезет на всем алгоритме)
ME>Сложность зануления можно принять как c * n, где с — константа.
Мне n-раз надо такую вещь делать. Т.е. (c*n)*n — если занулять.
ME>Тогда сложность будет O(x + c * n), т.е. зануление не должно оказать значительного влияния.
flax wrote:
>>> Занулять нельзя... тут вопросы с временной сложностью (иначе на каждом шаге n — зануляешь и n^2 -вылезет на всем алгоритме) > > ME>Сложность зануления можно принять как c * n, где с — константа. > > Мне n-раз надо такую вещь делать. Т.е. (c*n)*n — если занулять.
Ты меня не понял. Сложность зануления массива — c (memset), сложность зануления массива n раз — с * n.
Здравствуйте, flax, Вы писали:
F>Занулять нельзя...
по-моему обнулять все-таки придется — ведь нет никакой гарантии, что "неинициализированные, случайные значения" никогда не будут иметь допустимое значение ( x >= &a[0] && x < &a[n] ).
может лучше вместо массива указателей использовать какой-нибудь контейнер?
Здравствуйте, _grisha, Вы писали:
_>по-моему обнулять все-таки придется — ведь нет никакой гарантии, что "неинициализированные, случайные значения" никогда не будут иметь допустимое значение ( x >= &a[0] && x < &a[n] ).
Пусть случайные значения очень похожи на допустимые...
Массив А — весьма специальный, так что все вылавливается на следущем этапе.
Единственное (техническое) затруднение заключается в том, что
можно ли использовать в рабочем коде констукцию вида
Обвертка (exception){
x >= &a[0] && x < &a[n]
}
чтобы выловить указывает x в А или нет .
Смущения оттого, что вспоминается из книги какого-то гуру "Memory is not comparable!!!". Кстати почему? (только из-за возможности distributed размещения ресурсов памяти)
flax wrote:
> ME>А что, занулить массив P указателей перед использованием нельзя? Потом сравнивай указатели с нулем, в чем проблема? > > Занулять нельзя... тут вопросы с временной сложностью (иначе на каждом шаге n — зануляешь и n^2 -вылезет на всем алгоритме)
Здравствуйте, flax, Вы писали:
F>Здравствуйте, MaximE, Вы писали:
ME>>Ты меня не понял. Сложность зануления массива — c (memset), сложность зануления массива n раз — с * n.
F>I як, братцы, это (за константу) реализовать???
ME>Это действительно не константа, но ее время исполнения можно принять за константу, так как на каждой итерации он будет выполняться за константное время (если, конечно, размер твоего массива постоянен). Только если время выполнения memset будет равно времени исполнения одной итерации (что, как мне кажется, маловероятно), memset сможет повысить степень выражения асимптоматической сложности алгоритма.
1) Сложность алгоритма считается в наихудшем и асимптотическая ( в O()).
2) Размер P-массива равен n — и n может (считаем поведение на бесконечности) быть оЧень большим
3) Насколько я понимаю, memset есть (буквально)"оптимизированная версия пробежать первых n байт и заполнить их фиксированным значением". Т.е. ты говоришь, что он просто очень быстрый (если n-мало), не более того.
flax wrote:
> ME>Это действительно не константа, но ее время исполнения можно принять за константу, так как на каждой итерации он будет выполняться за константное время (если, конечно, размер твоего массива постоянен). Только если время выполнения memset будет равно времени исполнения одной итерации (что, как мне кажется, маловероятно), memset сможет повысить степень выражения асимптоматической сложности алгоритма.
> 1) Сложность алгоритма считается в наихудшем и асимптотическая ( в O()). > 2) Размер P-массива равен n — и n может (считаем поведение на бесконечности) быть оЧень большим
memset не работает на бесконечности
> 3) Насколько я понимаю, memset есть (буквально)"оптимизированная версия пробежать первых n байт и заполнить их фиксированным значением". Т.е. ты говоришь, что он просто очень быстрый (если n-мало), не более того.
Именно так. memset не увеличит количество итераций твоего алгоритма, лишь сделает каждую итерацию медленнее, поэтому memset не сделает из O(n * log(n)) алгоритма O(n^2) алгоритм.
Здравствуйте, MaximE, Вы писали:
>> 1) Сложность алгоритма считается в наихудшем и асимптотическая ( в O()). >> 2) Размер P-массива равен n — и n может (считаем поведение на бесконечности) быть оЧень большим
ME>memset не работает на бесконечности
Приколы приколами, а все же. Внутри все-равно цикл есть. Все-равно количество тактов процессора, которое тратится на выполнение memset, зависит от размера массива линейно.
Здравствуйте, LaptevVV, Вы писали:
F>>Что-то не похоже на константу? (n — большое) LVV>Там цепочечная команда рабьотает... До 256к на интеле одной командой...
А вот хотелось бы поразвернутее услышать про это чудо. Вы утверждаете, что 256к и 100 байтов обнуляются одно и то же (константное) время?
И, кстати, даже если 256к за одну команду, то для N байтов нужно N/256К команд, что, очевидно, есть O(N).
>> 3) Насколько я понимаю, memset есть (буквально)"оптимизированная версия пробежать первых n байт и заполнить их фиксированным значением". Т.е. ты говоришь, что он просто очень быстрый (если n-мало), не более того.
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), если она не константа, должна быть.
2) Если я правильно понял Lapteva, то реализация этой функции зашита в Intel-процессоры и способна (так же как мы считаем cкорость выполнения адресации в RandomAccessMemory к произвольному элементу за O(1)) на масштабах до 256к делать зануление последовательного куска памяти за O(1).
3) Но на бескончености ведь это даст ( в таком случае)
(n=size_of A)*(type_of A)/256k
т.е. те же O(n)
так?
Кстати
1) Почему в RAM доступ по адресу за O(1)? (в RAM она как постулат, а в компах — тоже на уровне инструкций проца)
2) Почему memory вообще говоря noncomparable, только для предоставления возможности менеджеру памяти без головной боли выполнять масштабирование?
Вадим Никулин 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 не знает).
Весьма интересно, и, честно говоря, выглядит пока что-то из разряда "чудеса и мистификации"
Здравствуйте, 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.
Здравствуйте, 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
F>"Вопрос о NonComparable"
F>Память NONcomparable. Т.е. на памяти введен лишь частичный порядок. Это сделано для того, чтобы менеджер памяти мог без головной боли перехать с одной машины на кластер
F>Так?
Я же не утверждаю ничего . Мне просто помнится (?!) что нейкий гуру, писал об этом. И у меня есть подозрения, что это был или Мейерс, или Элджер...
Здравствуйте, MaximE, Вы писали:
ME>Ok. Пусть количество итераций алгоритма i(n), сложность O(f(n)). Сложность memset на 32-битной платформе m(n) = c * n / 4. Добавление memset в каждую итерацию сделает O() алгоритма O(f(n) + i(n) * m(n)), т.е. не переводит алгоритм в (общую) группу с более высокой сложностью.
1) количество итераций = i(n) -пусть i(n) = тождественная, т.е. i(n)=n.
2) На каждой итерации что-то делалось, что в сумме давало n, т.е. если g(i) — количество операций на i-той итерации, то сумма по всем итерациям (т.е. сумма от 1 до i(n)=n выражений g(i)) равно n
3) Итак, на каждой итерации алгоритма создавался массив P длины n
-----------------------------------------------------------------
Если m(n) = c*n/4, то сложность алгоритма O(n*(c*n/4) + n)
Если m(n) = O(1), то O(n + n) = O(n)
Вот ещё один вопрос по архитектуре созрел.
Затраты на инициализацию справочника — это O(N).
Затраты на проверку валидности одного адреса — O(1).
Вопрос: сколько обращений к твоей таблице? Не дешевле ли единожды инициализировать, чем каждый раз проверять?
Профайлер покажет.
Впрочем, ты можешь действовать хитрым способом:
1) Если проверка выявила невалидный элемент, обнулить его.
Эта стратегия даст результат, когда промахов существенно больше, чем попаданий. Ведь невозможно отличить попадание от невалидного адреса, а вот повторный промах будет обработан гораздо быстрее.
2) Завести грубую карту инициализации. Скажем, разбить диапазон хеш-значений на 8N поддиапазонов, и каждому поддиапазону сопоставить 1 бит N-байтного массива признаков.
— Если бит =0 — значит, поддиапазон не инициализирован.
— — в случае чтения это означает заведомый промах.
— — в случае записи — выполняем инициализацию и взводим бит.
— Если бит =1 — значит, поддиапазон инициализирован.
— — чтение — никаких проверок
— — запись — установка единственного элемента.
flax wrote:
> Здравствуйте, MaximE, Вы писали: > > ME>Ok. Пусть количество итераций алгоритма i(n), сложность O(f(n)). Сложность memset на 32-битной платформе m(n) = c * n / 4. Добавление memset в каждую итерацию сделает O() алгоритма O(f(n) + i(n) * m(n)), т.е. не переводит алгоритм в (общую) группу с более высокой сложностью. > > 1) количество итераций = i(n) -пусть i(n) = тождественная, т.е. i(n)=n. > 2) На каждой итерации что-то делалось, что в сумме давало n, т.е. если g(i) — количество операций на i-той итерации, то сумма по всем итерациям (т.е. сумма от 1 до i(n)=n выражений g(i)) равно n > 3) Итак, на каждой итерации алгоритма создавался массив P длины n > > ----------------------------------------------------------------- > Если m(n) = c*n/4, то сложность алгоритма O(n*(c*n/4) + n) > Если m(n) = O(1), то O(n + n) = O(n)
Здравствуйте, Sergey, Вы писали:
S>Hello, flax! S>You wrote on Mon, 06 Dec 2004 10:12:50 GMT:
SDB>>> Фунукции IsBad*Ptr() не подойдут?
f>> Т.е. они помогут выловить, является ли значение в массиве P[i] вообще f>> указателем куда-либо или нет.
S>Они говорят ровно об одном — будет ли AV при записи/чтении по данному S>адресу.
http://weblogs.asp.net/larryosterman/archive/2004/05/18/134471.aspx
[quote]The way you check for bad pointers on Win32 is by calling the IsBadReadPtr and IsBadWritePtr API. Michael Howard calls these APIs “CrashMyApplication” and “CorruptMemoryAndCrashMySystem” respectively. The problem with IsBadReadPtr/IsBadWritePtr is that they do exactly what they’re advertised as doing: They read and/or write to the memory location specified, with an exception handler wrapped around the read/write. If an exception is thrown, they fail, if not, they succeed.[/quote]
Здравствуйте, flax, Вы писали:
F>Только тогда есть риск схватить что-то страшное при int x = P[i]: F> и надо иметь функцию Is_этавещь_Int() или просто ждать exception.
На какой архитектуре такие риски? Это с указателями ещё могут быть фокусы в сегментной модели... А тут всё просто — проверил диапазон, и настало тебе щастье.
Здравствуйте, flax, Вы писали:
F>Есть некоторый массив P указателей на int. В некоторые ячейки массива P были внесены указатели на элементы массива A (int), однако валидные значения были внесены не во все элементы P, и в некоторых ячейках массива P находятся неинициализированные, случайные значения ( то, что было на этом месте в памяти)
F>Можно ли, взяв произвольный указатель x из P (x = P[i]), проверить указывает ли он на (какой-либо) элемент F>массива (т.е. проверить указывает ли он в интервал памяти &a[0], &a[n-1]).
Нет, в рамках стандартного C/C++ эта задача неразрешима. Попытка доступа к значению неинициализированной переменной приводит к неопределенному поведению. Возможно получить доступ к внутреннему представлению такого объекта, трактуя его как массив байтов (unsigned char). Но стандарты C/C++ не дают никаких гарантий относительно внутреннего представления указателей. В частности, логически равные указатели (т.е. такие, для которых оператор = будет иметь значение true или 1) могут иметь различное внутреннее представление (т.е. memcmp для массивов байтов, представляющих эти указатели, может возвращать не ноль).
F>С одной стороны, вроде можно, обставив проверку exception-ом ( на нем будут выявляться те указатели, которые вообще указывают неизвестно куда).
Исключение вовсе не является стандартной реакцией на доступ к значению невалидного указателя. Здесь Вы говорите о какой-то конкретной реализации. Причем весьма экзотической.
F>С другой стороны, где-то слышал, что память вроде как не comparable.
Да, даже если бы в Вашем массиве P находились проинициализированные значения, указывающие на какие-то объекты, не входящие в массив A, то и в этом случае проверка их попадания в нужный диапазон была бы затруднена. Применение операторов <, >, <=, >= к указателям на объекты, не являющиеся подобъектами одного объекта или элементами одного массива, в C приводит к неопределенному поведению, а в C++ дает неспецифицированный результат. Остается лишь трудоемкое последовательное сравнение с адресами всех элементов массива при помощи операторов == или !=.
Hello, Centaur!
You wrote on Mon, 06 Dec 2004 17:10:16 GMT:
S>> Они говорят ровно об одном — будет ли AV при записи/чтении по данному S>> адресу.
C> http://weblogs.asp.net/larryosterman/archive/2004/05/18/134471.aspx C> [quote]The way you check for bad pointers on Win32 is by calling the C> IsBadReadPtr and IsBadWritePtr API. Michael Howard calls these APIs C> “CrashMyApplication” and “CorruptMemoryAndCrashMySystem” respectively. C> The problem with IsBadReadPtr/IsBadWritePtr is that they do exactly what C> they’re advertised as doing: They read and/or write to the memory C> location specified, with an exception handler wrapped around the C> read/write. If an exception is thrown, they fail, if not, they C> succeed.[/quote]
Да я в курсе, вообще-то Только сам проверял, а не Говарда читал.
With best regards, Sergey.
Posted via RSDN NNTP Server 1.9 delta
Одним из 33 полных кавалеров ордена "За заслуги перед Отечеством" является Геннадий Хазанов.
Перекуём баги на фичи!
Можно подробнее... что-то я запутался. 
!! 
. Мне просто помнится (?!) что нейкий гуру, писал об этом. И у меня есть подозрения, что это был или Мейерс, или Элджер... 
