Comments 55
Стоило бы расшифровать, что CL — CAS latency, tRCD — RAS to CAS delay, tRP — row precharge, CAS — column address strobe, RAS — row address strobe, а также объяснить откуда они берутся и зачем они нужны.
Если говорить о работе с dram в общем, то при массовом чтении она обычно выглядит следующим образом:
- выставили адрес строки,
- выставили RAS (и через такт сняли),
- выждали tRCD,
- выставили адрес колонки с которой читаем (и каждый следующий такт выставляем следующий номер колонки),
- выставили CAS,
- выждали CL, начали читать данные,
- сняли CAS, прочитали остаток данных (ещё CL тактов).
При переходе не следующий ряд делается precharge (RAS + WE), выжидается tRP, выполняется RAS с установленным адресом строки и далее выполняется чтение как описано выше.
Latency чтения случайной ячейки естественным образом вытекает из описанного выше: tRP + tRCD + CL.
операции чтения/записи ячеек строки группами по 4-8 бит/слов
Вам не показалось это странным, когда писали? 4-8 бит — это 1/2-1 байт, а 4-8 слов обычно 16-64 байта (в зависимости от размера слова). Шина SDRAM обычно не менее 32 бит, так что по 4-8 бит уж точно никто не читает.
Добавлю цитату.
В контексте «блока/таблицы памяти» выдача идет по битам, в контексте модуля по 64-битным словам, сами микросхемы могут иметь различную разрядность шины данных, из за чего зависит их количество на модуле памяти. В результате во время обращения к памяти идет пересылка 256/512 бит, или 32/64 байт, или 4/8 64-х битных слов. При этом не используется хранение байта целиком в одной строке одного блока памяти, он размещается побитно в 8-ми различных блоках памяти внутри одной или нескольких микросхем по идентичному геометрическому адресу «ROW x COL». Хотя ничего не мешает разместить все 64-битное слово в одной строке, но такой подход существенно замедлит операции последовательного чтения из за увеличения частоты смены строк. Так что мне не показалось странным указать что пересылка идет пакетом 4-8 бит/СЛОВ.
В контексте «блока/таблицы памяти» выдача идет по битам, в контексте модуля по 64-битным словам, сами микросхемы могут иметь различную разрядность шины данных, из за чего зависит их количество на модуле памяти. В результате во время обращения к памяти идет пересылка 256/512 бит, или 32/64 байт, или 4/8 64-х битных слов. При этом не используется хранение байта целиком в одной строке одного блока памяти, он размещается побитно в 8-ми различных блоках памяти внутри одной или нескольких микросхем по идентичному геометрическому адресу «ROW x COL». Хотя ничего не мешает разместить все 64-битное слово в одной строке, но такой подход существенно замедлит операции последовательного чтения из за увеличения частоты смены строк. Так что мне не показалось странным указать что пересылка идет пакетом 4-8 бит/СЛОВ.
А можно узнать, какую практическую задачу должно решать вот это все?
Т.е. в каких именно задачах из реального мира не хватает пропускной способности памяти?
Т.е. в каких именно задачах из реального мира не хватает пропускной способности памяти?
Пропускная способность памяти увеличена за счет количества каналов, теперь представьте себе ситуацию когда все необходимые данные расположены на одном модуле (вполне рабочая ситуация).
Проще решить вопрос с размером кэша 3-го уровня.
Не забывайте что кроме нужного 1 байта, вместе с ним прилетает в компании еще 31-63 байта. Для ситуации с обходом связных списков (деревьев), повышенная пропускная способность в купе с оптимизацией размещения данных, позволит ускорить обработку таблиц баз данных состоящих из количества рабочих элементов превышающих размер кэша.
Проще решить вопрос с размером кэша 3-го уровня.
Не забывайте что кроме нужного 1 байта, вместе с ним прилетает в компании еще 31-63 байта. Для ситуации с обходом связных списков (деревьев), повышенная пропускная способность в купе с оптимизацией размещения данных, позволит ускорить обработку таблиц баз данных состоящих из количества рабочих элементов превышающих размер кэша.
Нужно использовать оптимальные структуры данных, а не брутфорсить железом ситуацию, когда лишние байты неизбежно будут читаться вместе с необходимыми.
И так уже имеем ситуацию, когда в кармане у каждого лежит многоядерный компьютер, мощнее, чем любой суперкомпьютер 60-х годов или управляющий компьютер «Шаттла» или «Бурана», но используемый настолько неоптимально, что даже отрисовка UI на нем может тормозить.
КМК предложенные решения совершенно неоптимальны. Объем кэша ограничен отнюдь не «малой» длиной его строки, а «транзисторным бюджетом», т.е. размером кристалла, его стоимостью и энергопотреблением. Сверхдлинные строки кэша приведут к тому, что для доступа к одному байту придется читать уже не 31/63 лишних байта, а 4095. И когда понадобится освободить одну из строк кэша, в память придется записать целых 4 Кб, что почти на 2 порядка дольше записи стандартной 64-байтной строки. Соответственно, это катастрофически увеличит латентность. Предзагрузка в кэш реализована уже давным-давно, поэтому если встроенный prefetcher не справляется с каким-то хитрым шаблоном, то никто не мешает приложению самому загружать необходимые данные. Ну и т.п.
И так уже имеем ситуацию, когда в кармане у каждого лежит многоядерный компьютер, мощнее, чем любой суперкомпьютер 60-х годов или управляющий компьютер «Шаттла» или «Бурана», но используемый настолько неоптимально, что даже отрисовка UI на нем может тормозить.
КМК предложенные решения совершенно неоптимальны. Объем кэша ограничен отнюдь не «малой» длиной его строки, а «транзисторным бюджетом», т.е. размером кристалла, его стоимостью и энергопотреблением. Сверхдлинные строки кэша приведут к тому, что для доступа к одному байту придется читать уже не 31/63 лишних байта, а 4095. И когда понадобится освободить одну из строк кэша, в память придется записать целых 4 Кб, что почти на 2 порядка дольше записи стандартной 64-байтной строки. Соответственно, это катастрофически увеличит латентность. Предзагрузка в кэш реализована уже давным-давно, поэтому если встроенный prefetcher не справляется с каким-то хитрым шаблоном, то никто не мешает приложению самому загружать необходимые данные. Ну и т.п.
Задачка на масштабирование обработки данных
есть связный список из N элементов
«указатель на следующий элемент», «некое число 32 бит для сравнения (не равно 0)», «32-х битное число для инкремента (заставить строку кэша записаться назад в память)», «32-х битное число для выравнивания» — итого L=16 байт.
Обход списка оценивается как O=N
Из этого можно предположить что многократная обработка займет пропорциональное время в следующих ситуациях:
N=(100*N)/100=(1000*N)/1000
X=Z*N -> N=(100*X)/(100*Z)
Однако если «X * L» превысит объем кэша, если скорость обработки данных превысит скорость доступа к данным (которая может быть увеличена только за счет многоканальности), никакая оптимизация не поможет сохранить отношение:
N = (100*1)/100 = (100*N)/100 = (100*X)/(100*Z) при N*L*16 < K < X*L, и X = Z * N
Здесь 16 это множитель с запасом для уменьшения влияния канальности кэша.
Сможете доказать обратное?
HINT: самая быстрая скорость обработки будет в ситуации когда элементы списка размещены последовательно друг за другом.
i7-3820 с частотой 3600 МГц и памятью DDR3-1600 обрабатывал списки (длиной 1,100, 1000) размещенные в кэше с темпом 2,5 нс на элемент
обработка списка из 1 000 000 элементов была с темпом 2,96 нс для 4-х канальной памяти, 3 нс для 2-х канальной, и 3,5 нс для одноканальной памяти. При этом был не самый быстрый «код», можно сделать и побыстрее.
Кстати Pentium E5700 с частотой 3000 МГц обрабатывал списки в кэше с темпом 2,1 нс и 9,8 нс при доступе к памяти, это к вопросу что размер кэша не влияет на скорость доступа к нему.
К этому можно добавить что память использовалась только одним потоком (защищенный 32-х битный режим без инициализации многопоточности), а что будет если память начнут терзать несколько ядер, причем в конкурентном режиме при прочей оптимизации.
есть связный список из N элементов
«указатель на следующий элемент», «некое число 32 бит для сравнения (не равно 0)», «32-х битное число для инкремента (заставить строку кэша записаться назад в память)», «32-х битное число для выравнивания» — итого L=16 байт.
Обход списка оценивается как O=N
Из этого можно предположить что многократная обработка займет пропорциональное время в следующих ситуациях:
N=(100*N)/100=(1000*N)/1000
X=Z*N -> N=(100*X)/(100*Z)
Однако если «X * L» превысит объем кэша, если скорость обработки данных превысит скорость доступа к данным (которая может быть увеличена только за счет многоканальности), никакая оптимизация не поможет сохранить отношение:
N = (100*1)/100 = (100*N)/100 = (100*X)/(100*Z) при N*L*16 < K < X*L, и X = Z * N
Здесь 16 это множитель с запасом для уменьшения влияния канальности кэша.
Сможете доказать обратное?
HINT: самая быстрая скорость обработки будет в ситуации когда элементы списка размещены последовательно друг за другом.
i7-3820 с частотой 3600 МГц и памятью DDR3-1600 обрабатывал списки (длиной 1,100, 1000) размещенные в кэше с темпом 2,5 нс на элемент
обработка списка из 1 000 000 элементов была с темпом 2,96 нс для 4-х канальной памяти, 3 нс для 2-х канальной, и 3,5 нс для одноканальной памяти. При этом был не самый быстрый «код», можно сделать и побыстрее.
код ассемблера
xor edx, edx
mov ebx, ds:[start_pointer]
next:
cmp ebx, 0
jne @f
ret
@@:
inc dword ptr es:[ebx+12]
mov eax, es:[ebx]
mov ebx, eax
inc edx
dec ecx
jnz next
ret
mov ebx, ds:[start_pointer]
next:
cmp ebx, 0
jne @f
ret
@@:
inc dword ptr es:[ebx+12]
mov eax, es:[ebx]
mov ebx, eax
inc edx
dec ecx
jnz next
ret
Кстати Pentium E5700 с частотой 3000 МГц обрабатывал списки в кэше с темпом 2,1 нс и 9,8 нс при доступе к памяти, это к вопросу что размер кэша не влияет на скорость доступа к нему.
К этому можно добавить что память использовалась только одним потоком (защищенный 32-х битный режим без инициализации многопоточности), а что будет если память начнут терзать несколько ядер, причем в конкурентном режиме при прочей оптимизации.
1. Я нигде не утверждал, что размер кэша не влияет на скорость доступа. Я утверждал, что в существующих условиях размер кэша ограничен не малой длиной строки, а стоимостью и энергопотреблением.
2. Утверждение о том, что темп для данных в кэше и в памяти таков-то без указания в каком именно кэше не имеет смысла. В процессорах, начиная с архитектуры Nehalem латентность кэша L1D выросла с 3 до 4 тактов. А латентность доступа к Last Level Cache (L2 у Wolfdale и L3 у Ivy Bridge) при сравнимом объеме у Wolfdale вообще двое ниже — 15 тактов против ~30. Так что пока данные умещаются в L1D или превышают объем L2 Ivy Bridge, но умещаются в L2 Wolfdale последний будет быстрее, даже несмотря на меньшую частоту именно благодаря значительно меньшей латентности кэша. Но как только объем данных значительно превысит размер кэша, любой процессор с интегрированным контроллером памяти (iMC) будет превосходить по скорости работы процессор без IMC буквально в разы.
3. Я недаром спрашивал про ПРАКТИЧЕСКУЮ задачу, которую должно решать глобальное изменение архитектуры. Как и ожидалось, вместо практической задачи представлен сферический конь в вакууме, где как минимум 25% объема памяти теряется на абсолютно бессмысленное выравнивание, соответственно 25% объема кэша и 25% ПСП теряются впустую.
4. Мне неясен философский смысл инкремента edx и декремента ecx в приведенном ассемблерном коде. Они никуда не записываются и ни с чем не сравниваются.
Итого. Будет реальная задача, для которой так уж необходима глобальная перестройка всей архитектуры компьютеров? Естественно с кодом. С полным кодом, а не выдранным куском. Который можно скомпилировать/сассемблировать, измерить скорость, оптимизировать и т.п.
2. Утверждение о том, что темп для данных в кэше и в памяти таков-то без указания в каком именно кэше не имеет смысла. В процессорах, начиная с архитектуры Nehalem латентность кэша L1D выросла с 3 до 4 тактов. А латентность доступа к Last Level Cache (L2 у Wolfdale и L3 у Ivy Bridge) при сравнимом объеме у Wolfdale вообще двое ниже — 15 тактов против ~30. Так что пока данные умещаются в L1D или превышают объем L2 Ivy Bridge, но умещаются в L2 Wolfdale последний будет быстрее, даже несмотря на меньшую частоту именно благодаря значительно меньшей латентности кэша. Но как только объем данных значительно превысит размер кэша, любой процессор с интегрированным контроллером памяти (iMC) будет превосходить по скорости работы процессор без IMC буквально в разы.
3. Я недаром спрашивал про ПРАКТИЧЕСКУЮ задачу, которую должно решать глобальное изменение архитектуры. Как и ожидалось, вместо практической задачи представлен сферический конь в вакууме, где как минимум 25% объема памяти теряется на абсолютно бессмысленное выравнивание, соответственно 25% объема кэша и 25% ПСП теряются впустую.
4. Мне неясен философский смысл инкремента edx и декремента ecx в приведенном ассемблерном коде. Они никуда не записываются и ни с чем не сравниваются.
Итого. Будет реальная задача, для которой так уж необходима глобальная перестройка всей архитектуры компьютеров? Естественно с кодом. С полным кодом, а не выдранным куском. Который можно скомпилировать/сассемблировать, измерить скорость, оптимизировать и т.п.
Я утверждал, что в существующих условиях размер кэша ограничен не малой длиной строки, а стоимостью и энергопотреблением.Если бы. Вы знаете сколько стоит и потребляет какой-нибудь POWER8? А у него ведь кеш такого же размера, как у всех: всё те же 64K.
Это физическое ограничение — выше головы не прыгнешь.
Остальное — всё верно.
Можно узнать какие физические законы нарушает кэш размером более 64К?
Причём тут физические законы? Тут простая банальная логика. Процессорное ядро и кеш должны быть сравнимы по размерам и, стало быть, по количеству транзисторов. Кеш может быть чуть больше, так как провода там «прямее», но не сильно. Два кеша по 64K кеша требуют, грубо, 5-6 миллионов транзисторов (4-6 на ячейку SRAM плюс ещё нужно тегирование и прочие накладыне расходы) — то есть как раз примерно столько же, сколько занимает современное процессорное ядро.
Можно сделать больше? Да, конечно. Но смысл? Придётся снижать частоту всей системы, что в 99 случаях из 100 даст в результате проигрыш.
Можно сделать больше? Да, конечно. Но смысл? Придётся снижать частоту всей системы, что в 99 случаях из 100 даст в результате проигрыш.
Частоту системы не приходится снижать даже для многомегабайтных кэшей L3.
Еще попытка?
Еще попытка?
Частоту системы не приходится снижать даже для многомегабайтных кэшей L3.Процессор отдающий данные за 4 такта из «многомегабайтного кеша L3» — в студию!
Еще попытка?А может хватит изображать из себя идиота, а?
Идиота тут скорее изображаете именно вы.
Не надо путать ПСП и латентность. ПСП зависит от ширины шины и частоты. А латентность еще и от организации кэша.
Не надо путать ПСП и латентность. ПСП зависит от ширины шины и частоты. А латентность еще и от организации кэша.
ПСП зависит от ширины шины и частоты.Это ещё с какого перепугу? Кто вам сказал что кеш L3 (или, тем более, оперативная память) смогут вам каждый такт данные поставлять?
А латентность еще и от организации кэша.Тут вы правы, но лишь отчасти. Плохая организация кеша может её увеличть, но никакая организация кеша не сможет её ускорить. Кеш L3 как выдавал данные за десятки тактов, так и выдаёт. И ничего вы с этим не сделаете.
Домашнее задание: подумать над тем как увеличит скорость работы кеша увеличение частоты на которой он работает. Как поймёте почему правильный ответ «теоретически в предельном случае можно достигнуть увеличения скорости в два раза, но на практике эффект не превышает 20-30%» — заходите, будет о чём поговорить.
Знаете, я не заметил, чтобы вы были ведущим инженером-архитектором Intel или IBM, чтобы с таким апломбом выдавать мне «домашнее задание».
И стоит избавиться от идиотской привычки возражать на то, чего оппонент никогда не говорил.
Независимо от того, может или не может L3 кэш выдавать данные каждый такт, его ПСП прямо пропорциональна тактовой частоте, его латентность в тактах от частоты не зависит, а в наносекундах — обратно пропорциональна ей.
Как только сможете тестами опровергнуть это — заходите, будет о чем поговорить.
И стоит избавиться от идиотской привычки возражать на то, чего оппонент никогда не говорил.
Независимо от того, может или не может L3 кэш выдавать данные каждый такт, его ПСП прямо пропорциональна тактовой частоте, его латентность в тактах от частоты не зависит, а в наносекундах — обратно пропорциональна ей.
Как только сможете тестами опровергнуть это — заходите, будет о чем поговорить.
1. Объем кэша 3-го уровня превышает 10 мб, однако скорость доступа к нему гораздо медленнее по простой причине: время необходимое выждать чтобы каждый из элементов строк кэша смог проверить соответствие хранимой информации, запрошенному адресу выше для большего количества элементов.
3. База данных с количеством элементов, индексное поле которой превышает в несколько раз объем кэша. Конечно, это задача из разряда «640 кб, этого объема должно хватить всем»
4. edx — рудимент, проверить что количество циклов соответствует заданному количеству, связный список зациклен, те сначала идет подготовка списка из N-элементов, при этом последний элемент ссылается на первый.
ecx — если внимательно посмотреть, определяет «выход» по достижению заданного количества циклов. Команда DEC при получении 0 в уменьшаемой переменной обнуляет флаг Z, дальше идет JNZ который осуществляет переход если флаг нуля не говорит что был ноль. Но видимо нужно было поставить:
DEC ECX
CMP ECX, 0
JNZ NEXT
проверка «cmp ebx,0» это «имитация бурной деятельности», в реальности список зациклен, и ebx не получает 0.
2. «чисто для смеха» я уменьшил код до:
next:
inc dword ptr es:[ebx+12]
mov ebx, es:[ebx]
dec ecx
jnz next
ret
под рукой был только Atom-1600 MHz и i7-980 3333 MHz 3ch DDR3-1600
будут четыре значения соответсвующие длинному и короткому коду для атома и для i7
записей/количество циклов
100/10: 3,4 / 2,5 / 3,0 / 1,5
1000/10: 3,4 / 2,5 / 3,0 / 1,5
1млн/20: 15 / 14,87 / Х / 5 (лень было восстановить длинный код, поэтому измерения нет)
1млн/60: 14,9 / 14,9 / X / 4,8
1/10000: 3,4 / 2,5 / 3,0 / 1,5 (Да, это интенсивная обработка 16 байт)
1/100: 4,7 / 3,6 / 3,2 / 1,7
(если кому интересно то отключение кэширования замедляет работу в 100-1000 раз
а старенький Xeon судя по результатам измерений, сделал вид что ему кэш не отключали)
тактовая частота 1600 = 0,625 нс / 3333 = 0,3 нс
3,4 нс = 5+ тактов, 15 нс = 24 такта
1,5 нс = 5 тактов процессора i7 (4 активных команды, в принципе совпадает)
5 нс = порядка 16 тактов (погодите, только что тот-же процессор все делал за 5-6 тактов)
наблюдается четкая разница в 3 раза для работы встроенного контроллера, между работой с данными в кэше и с данными в памяти
ДЛЯ ЖУТКО ОПТИМИЗИРОВАННЫХ ДАННЫХ но разного объема.
Реальная задача на текущий момент это обработка больших объемов информации. Для примера можно взять хоть и не совсем удачный пример Учёт в муравейнике.
3. База данных с количеством элементов, индексное поле которой превышает в несколько раз объем кэша. Конечно, это задача из разряда «640 кб, этого объема должно хватить всем»
4. edx — рудимент, проверить что количество циклов соответствует заданному количеству, связный список зациклен, те сначала идет подготовка списка из N-элементов, при этом последний элемент ссылается на первый.
ecx — если внимательно посмотреть, определяет «выход» по достижению заданного количества циклов. Команда DEC при получении 0 в уменьшаемой переменной обнуляет флаг Z, дальше идет JNZ который осуществляет переход если флаг нуля не говорит что был ноль. Но видимо нужно было поставить:
DEC ECX
CMP ECX, 0
JNZ NEXT
проверка «cmp ebx,0» это «имитация бурной деятельности», в реальности список зациклен, и ebx не получает 0.
2. «чисто для смеха» я уменьшил код до:
next:
inc dword ptr es:[ebx+12]
mov ebx, es:[ebx]
dec ecx
jnz next
ret
под рукой был только Atom-1600 MHz и i7-980 3333 MHz 3ch DDR3-1600
будут четыре значения соответсвующие длинному и короткому коду для атома и для i7
записей/количество циклов
100/10: 3,4 / 2,5 / 3,0 / 1,5
1000/10: 3,4 / 2,5 / 3,0 / 1,5
1млн/20: 15 / 14,87 / Х / 5 (лень было восстановить длинный код, поэтому измерения нет)
1млн/60: 14,9 / 14,9 / X / 4,8
1/10000: 3,4 / 2,5 / 3,0 / 1,5 (Да, это интенсивная обработка 16 байт)
1/100: 4,7 / 3,6 / 3,2 / 1,7
(если кому интересно то отключение кэширования замедляет работу в 100-1000 раз
а старенький Xeon судя по результатам измерений, сделал вид что ему кэш не отключали)
тактовая частота 1600 = 0,625 нс / 3333 = 0,3 нс
3,4 нс = 5+ тактов, 15 нс = 24 такта
1,5 нс = 5 тактов процессора i7 (4 активных команды, в принципе совпадает)
5 нс = порядка 16 тактов (погодите, только что тот-же процессор все делал за 5-6 тактов)
наблюдается четкая разница в 3 раза для работы встроенного контроллера, между работой с данными в кэше и с данными в памяти
ДЛЯ ЖУТКО ОПТИМИЗИРОВАННЫХ ДАННЫХ но разного объема.
Реальная задача на текущий момент это обработка больших объемов информации. Для примера можно взять хоть и не совсем удачный пример Учёт в муравейнике.
Начнем с конца. «Учет в муравейнике» — это I/O bound задача. Причем даже не I/O памяти, а практически безумно медленного по сравнению с процессором HDD. Так что никакое увеличение ПСП памяти там не поможет принципиально.
Далее. Объем L3 кэша среднего Core i5 и старших 2-ядерных Wolfdale равны (по 6 МБ). При этом у Wolfdale вдвое выше ассоциативность и вдвое же ниже латентность. Так что количество строк само по себе на скорость не влияет.
Еще далее. Не нужны пустые слова. Нужна КОНКРЕТНАЯ практическая задача. Пока вижу сферического коня в вакууме. И он стал еще сферичнее, а вакуум еще глубже.
Т.е. по сути никакой практической задачи нет и не предвидится. Есть гениальная задумка, для доказательства которой приводится абсолютно бессмысленный тест. Ну да, если вам действительно нужно исполнять с предельной скоростью эти 5 инструкций в такой последовательности, то всенепременно нужно потратить триллионы долларов, чтобы кардинально поменять архитектуру компьютеров.
Причем даже в этой совершенно вырожденной задаче ПОЛОВИНА ПСП и объема кэша тратится совершенно впустую. Потому что мало того, что используется абсолютно бессмысленное выравнивание, так еще и второй элемент вообще никак не используется.
Далее. Объем L3 кэша среднего Core i5 и старших 2-ядерных Wolfdale равны (по 6 МБ). При этом у Wolfdale вдвое выше ассоциативность и вдвое же ниже латентность. Так что количество строк само по себе на скорость не влияет.
Еще далее. Не нужны пустые слова. Нужна КОНКРЕТНАЯ практическая задача. Пока вижу сферического коня в вакууме. И он стал еще сферичнее, а вакуум еще глубже.
Т.е. по сути никакой практической задачи нет и не предвидится. Есть гениальная задумка, для доказательства которой приводится абсолютно бессмысленный тест. Ну да, если вам действительно нужно исполнять с предельной скоростью эти 5 инструкций в такой последовательности, то всенепременно нужно потратить триллионы долларов, чтобы кардинально поменять архитектуру компьютеров.
Причем даже в этой совершенно вырожденной задаче ПОЛОВИНА ПСП и объема кэша тратится совершенно впустую. Потому что мало того, что используется абсолютно бессмысленное выравнивание, так еще и второй элемент вообще никак не используется.
Обход двоичных деревьев достаточно реальная задача?
2 указателя, 1 сравнение, 1 нагрузка для выравнивания.
Ограничиваемся 32-х битными значениями. Предложите «эффективную структуру/алгоритм» для текущей архитектуры, я предложу свои «теоретические расчеты и алгоритм».
Завтра встречаемся здесь же.
2 указателя, 1 сравнение, 1 нагрузка для выравнивания.
Ограничиваемся 32-х битными значениями. Предложите «эффективную структуру/алгоритм» для текущей архитектуры, я предложу свои «теоретические расчеты и алгоритм».
Завтра встречаемся здесь же.
Это может быть и реальная задача, которую предложили решить студенту. Но при этом очередной бессмысленный сферический конь в вакууме.
Я спрашивал про ПРАКТИЧЕСКУЮ задачу. Система продажи билетов, например. Тот же «муравейник». Разница понятна?
Из практической задачи естественным образом вытекают ее ограничения. А в сферической задаче в вакууме они придуманы произвольным образом.
Практическую задачу можно решать с помощью различных алгоритмов и структур данных. И совсем не обязательно это будут двоичные деревья.
А у вас опять совершенно вырожденный случай, где деревья не несут никакой полезной информации — есть ключ, есть 2 указателя, есть совершенно бессмысленное выравнивание, а никаких хранимых данных нет. Ок, можно «выравнивание» посчитать полезной нагрузкой. Вы действительно считаете, что структура с 75% служебных и 25% полезных данных оптимальна?
Я спрашивал про ПРАКТИЧЕСКУЮ задачу. Система продажи билетов, например. Тот же «муравейник». Разница понятна?
Из практической задачи естественным образом вытекают ее ограничения. А в сферической задаче в вакууме они придуманы произвольным образом.
Практическую задачу можно решать с помощью различных алгоритмов и структур данных. И совсем не обязательно это будут двоичные деревья.
А у вас опять совершенно вырожденный случай, где деревья не несут никакой полезной информации — есть ключ, есть 2 указателя, есть совершенно бессмысленное выравнивание, а никаких хранимых данных нет. Ок, можно «выравнивание» посчитать полезной нагрузкой. Вы действительно считаете, что структура с 75% служебных и 25% полезных данных оптимальна?
Насчет сферических коней в вакууме это вы физикам скажите. У них сначала «сферический конь в вакууме» в теории образуется, а потом они строят всякие ускорители за миллиарды, чтобы подтвердить или опровергнуть существование этого коня.
качаем отсюда архивчик
Планируем сервис по определению действительности паспорта из расчета однопоточного приложения.
качаем отсюда архивчик
Планируем сервис по определению действительности паспорта из расчета однопоточного приложения.
Сферический конь в вакууме образовался у физиков не в теории, а в анекдоте. Именно как случай крайнего вырождения модели, которая и близко не напоминает оригинал.
Ну, ОК. Скачал я эту базу и распаковал. Имеем файл примерно со ~100 млн. записей.
Насколько я понимаю, требуется по вводимым серии и номеру определить есть ли паспорт среди недействительных.
Какова частота обновления самой базы? Какова архитектура машины, на которой это должно работать (х86/х64)?
Ну, ОК. Скачал я эту базу и распаковал. Имеем файл примерно со ~100 млн. записей.
Насколько я понимаю, требуется по вводимым серии и номеру определить есть ли паспорт среди недействительных.
Какова частота обновления самой базы? Какова архитектура машины, на которой это должно работать (х86/х64)?
И вдогонку: ваши предложения по структурам данных и алгоритмам.
На ваш выбор, должно быть быстро, и в разумных пределах (по расходу памяти). Хочу отдельно отметить что там есть номера старого формата с римскими числами «XX-М,559701» так что:
Средняя длина номера паспорта 12 символов включая разделитель и символ в запас.
Ограничимся кодовой таблицей из 256 символов но на каждом месте.
Может получится в «интерпол» продать алгоритм, там может понадобиться широкий диапазон вариантов номеров.
Средняя длина номера паспорта 12 символов включая разделитель и символ в запас.
Ограничимся кодовой таблицей из 256 символов но на каждом месте.
Может получится в «интерпол» продать алгоритм, там может понадобиться широкий диапазон вариантов номеров.
Вы опять превращаете конкретную практическую задачу в сферического коня.
Для задачи быстрого поиска недействительных российских паспортов мы можем взять априорные знания о том каким может и не может быть этот номер.
Плюс важна частота обновления этих данных, от этого тоже многое зависит.
Быстрый поиск недействительных российских паспортов — это одно, быстрый поиск всего чего угодно неизвестного заранее объема и длины — это совершенно другое. «Средняя длина» и «ограничимся» — это как раз то самое превращение коня с 4 ногами в шар.
И, кстати, номера советских паспортов в этой базе — нонсенс. Серия банально не умещается в заданном поле, это ошибочные данные, которые нужно отфильтровывать, а не обрабатывать, потому что корректно обработать их (реально, а не формально) просто невозможно.
Для задачи быстрого поиска недействительных российских паспортов мы можем взять априорные знания о том каким может и не может быть этот номер.
Плюс важна частота обновления этих данных, от этого тоже многое зависит.
Быстрый поиск недействительных российских паспортов — это одно, быстрый поиск всего чего угодно неизвестного заранее объема и длины — это совершенно другое. «Средняя длина» и «ограничимся» — это как раз то самое превращение коня с 4 ногами в шар.
И, кстати, номера советских паспортов в этой базе — нонсенс. Серия банально не умещается в заданном поле, это ошибочные данные, которые нужно отфильтровывать, а не обрабатывать, потому что корректно обработать их (реально, а не формально) просто невозможно.
На входе получаем строку из серии и номера паспорта, входные символы должны быть ограничены таблицей из 256 символов.
Делим символ на две половины, каждую половину представляем в виде узла из 16 указателей.
12 символов это дерево глубиной в 24 символа, при этом мы получаем динамическую структуру которой можно описать и более длинные строки. 50 нс * 24 прохода = 1,2 — 1,5 мкс, максимальное время поиска.
Это просто задача в лоб без учета «экономии», решить ее таким образом можно? можно.
Можно использовать таблицу указателей из 256 записей, тогда время поиска уменьшиться в два раза.
Делим символ на две половины, каждую половину представляем в виде узла из 16 указателей.
12 символов это дерево глубиной в 24 символа, при этом мы получаем динамическую структуру которой можно описать и более длинные строки. 50 нс * 24 прохода = 1,2 — 1,5 мкс, максимальное время поиска.
Это просто задача в лоб без учета «экономии», решить ее таким образом можно? можно.
Можно использовать таблицу указателей из 256 записей, тогда время поиска уменьшиться в два раза.
Чет я ступил, в 4096 байт влезет корень из 16 записей, и еще 16 по 16 = 256 указателей (1088 байт).
Что автоматически ускоряет поиск до 0,6-0,75 мкс.
Что автоматически ускоряет поиск до 0,6-0,75 мкс.
Меня всегда умиляет, как люди умудряются отвечать на вопросы, которые им не задавали.
Вот объясните мне, каким образом из конкретной практической задачи поиска номеров недействительных паспортов вырастают уши у задачи поиска произвольной строки длиной почему-то 12 символов?
Для конкретной практической задачи поиска номера паспорта все эти ваши деревья не нужны абсолютно. Соответственно, и предложения по глобальному изменению архитектуры, которые вытекают из вашего маниакального желания использовать для поиска в данном случае именно двоичные деревья — тоже.
Если вы разрабатываете новый академический алгоритм поиска строки — это совершенно другая история. Но даже в этом случае логично менять именно алгоритм, учитывая особенности железа, а не наоборот.
Вот объясните мне, каким образом из конкретной практической задачи поиска номеров недействительных паспортов вырастают уши у задачи поиска произвольной строки длиной почему-то 12 символов?
Для конкретной практической задачи поиска номера паспорта все эти ваши деревья не нужны абсолютно. Соответственно, и предложения по глобальному изменению архитектуры, которые вытекают из вашего маниакального желания использовать для поиска в данном случае именно двоичные деревья — тоже.
Если вы разрабатываете новый академический алгоритм поиска строки — это совершенно другая история. Но даже в этом случае логично менять именно алгоритм, учитывая особенности железа, а не наоборот.
Какой-же Вы скучный человек, даже ругаться с вами скучно. Сидите спокойно себе на готовых технологиях. Покупайте всегда свеженький ифончик, а я пойду еще пару нелепых идей придумаю.
Как я люблю людей, которые мнят себя великими новаторами, но при этом мыслят штампами. Это я про «свеженький ифончик».
А вы, да, продолжайте придумывать нелепые идеи.
Только не рассчитывайте, что они вдруг станут революционными. Потому что пока я вижу натягивание совы на глобус. Совершенно ненужное и баснословно дорогое. И вряд ли в других нелепых идеях это как-то изменится.
А вы, да, продолжайте придумывать нелепые идеи.
Только не рассчитывайте, что они вдруг станут революционными. Потому что пока я вижу натягивание совы на глобус. Совершенно ненужное и баснословно дорогое. И вряд ли в других нелепых идеях это как-то изменится.
Из «законов Мерфи»: «Чтобы вы не делали, как бы не хорош был ваш поступок, всегда найдется недовольный человек».
Что такого баснословно дорогого в этой реализации? чисто поржать.
Что такого баснословно дорогого в этой реализации? чисто поржать.
Ну так вы реализуйте свой подход, раз он недорог. Покажите всем его преимущества. Глядишь, люди к вам и потянутся. Какой нибудь Intel купит патент за миллиард-другой.
А менять архитектуру подсистемы памяти только из-за того, что кто-то применяет неоптимальные алгоритмы и структуры данных никто не будет.
И прикрываться «Законами Мерфи» не стоит. Во-первых, я пока не вижу вообще никакого поступка. И тем более нет ничего хорошего в идее брутфорсить железом неоптимальность софта.
А менять архитектуру подсистемы памяти только из-за того, что кто-то применяет неоптимальные алгоритмы и структуры данных никто не будет.
И прикрываться «Законами Мерфи» не стоит. Во-первых, я пока не вижу вообще никакого поступка. И тем более нет ничего хорошего в идее брутфорсить железом неоптимальность софта.
Кстати Pentium E5700 с частотой 3000 МГц обрабатывал списки в кэше с темпом 2,1 нс и 9,8 нс при доступе к памяти, это к вопросу что размер кэша не влияет на скорость доступа к нему.Думалку включить слабо? Вы перепутали причину и следствие. Hint: процессор, выпущенный четверть века назад имел кеш в 32K, к началу XXI века объём был доведён до 64K — и такой же кеш в процессорах, выпускающихся сегодня.
Никто не стал бы создавать всех эти кеши 2го, 3го, 4го уровня, если бы «размер кеша не влиял на скорость доступа к нему». Влияет и ещё как! На полную частоту получается сделать32K-64K, не больше. ZX Spectrum работающий 5GHz с соотвествующей памятью сегодня, скорее всего, сделать удастся. А вот компьютер с гигабайтом или терабайтом оперативки — нет. И ничего ваши «широкие» каналы не изменят, только усложнят работу кеша. Больше 64K его сделать не удаётся, а размер строки в 4K при кеге в 64K — бессмысленен.
Боюсь, вы в корне заблуждаетесь.
ВСЕ кэши процессоров Sandy Bridge, Ivy Bridge и Haswell работают на «полной частоте».
ВСЕ кэши процессоров Sandy Bridge, Ivy Bridge и Haswell работают на «полной частоте».
ВСЕ кэши процессоров Sandy Bridge, Ivy Bridge и Haswell работают на «полной частоте».Это что за чушь? Какой бы в них был смысл если бы так всё было? Оставили бы L3 и всё.
Или вы имеете в виду что в них сигнал синхронизации поноскоростной поступает? А какая разница?
Отдать данные они могут только на пониженной в 3-4 раза (L1) скорости, а то и в 15-30 раз (L2, L3, etc) скорости. А программе, в общем, без разницы какая частота заведена в какие части системы, тут время в наносекундах решает :-) Ну или в циклах (если вы хотим сравнивать не конкретные процессоры, а архитектуры). А в циклах — всё работает примерно так.
И если подумать то, в общем, сложно сделать чтобы оно работало по другому. Поднять ПСП кешей, конечно, можно, но без изменения архитектуры это всё — мёртвому припарки, так как задержки-то от этого не уменьшатся — скорее возростут!
Смысл именно в том, что ПСП и латентность — величины в некоторой степени ортогональные.
А такой величины как «скорость» в данном случае вообще не существует.
А такой величины как «скорость» в данном случае вообще не существует.
А такой величины как «скорость» в данном случае вообще не существует.Это кто ж вам такую чушь сказал? Скорость — это произведение ширины шины время доставки данных.
Теоретически скорость можно повысить до заоблачных величин за счёт увеличения ширины шины, но практически — нет: чем «шире» у вас канал, тем выше задержки, но главное — задачи, выполняемые на CPU, гораздо более чувствительны именно к задержкам. Повышать ПСП за счёт увеличения задержек — чревато замедлением программ, а не ускорением.
На GPU — жизнь другая, там максимальная осмысленная ширина шины гораздо больше.
Насколько я помню, я не заявлял что размер кэша не влияет на скорость доступа к нему, и связано это со временем ожидания пока все элементы списка получат адрес, проверят соответствие, и самый дальний (по сигналу) пошлет ответ «у меня! у меня есть эти данные».
Не забывайте что кроме нужного 1 байта, вместе с ним прилетает в компании еще 31-63 байта. Для ситуации с обходом связных списков (деревьев)… это приводит к тому, что увеличение «ширины» канала приводит к тому, что вы начинаете сильнее нагревать окружающаю среду — и только.
повышенная пропускная способность в купе с оптимизацией размещения данныхТак вы деревья обходите или «оптимизируете размещение данных»? Если первое, то «широкий» канал вам только мешать будет — и вы это сами только что объяснили. Если вы хотите «оптимизировать данные», то к вашим услугам GPU и HBM.
Вы уж определитесь — чего вы хотите, а потом и обсуждать можно.
О эти диаграммы из Экселя…
Не увидел раздела «Ссылки», но без сомнений для всех заинтересовавшихся пригодится книга «Что каждый программист должен знать о памяти» — rus-linux.net/lib.php?name=/MyLDP/hard/memory/memory.html
Вашу бы изобретательность да на доработку программных алгоритмов…
Ничего не поможет. Этим занимаются десятки тысяч программистов, но проблема в том, что любые их достижения с готовностью «просираются», когда «миллионы хомячков» используют их, чтобы построить ещё более высокую башню технологий. Потери на каждом «этаже» это баншли вроде невелики (где-то 20-30%), но при наличии 10-20 этажей оказывается, что 99% ресурсов современных компьютеров уходит, грубо говоря, «в песок».
В случае необходимости в этой башне пробивается «дыра» для решения какой-то задачи — и тогда получается, что «в песок» уходит не 99% ресурсов, а, скажем, 90%. Иногда даже, о боги, «в дело» идёт 90%!
Но вообще — законы Натана действуют. Особенно первый.
В случае необходимости в этой башне пробивается «дыра» для решения какой-то задачи — и тогда получается, что «в песок» уходит не 99% ресурсов, а, скажем, 90%. Иногда даже, о боги, «в дело» идёт 90%!
Но вообще — законы Натана действуют. Особенно первый.
Сдаётся мне, операционки не «хомяки» пишут. Так почему это сейчас чтобы запустить окошки нужно минимум в десять раз больше мощности чем 15 лет назад?
Можете не отвечать, я знаю почему. Это был скорее риторический вопрос, к вопросу о улучшении алгоритмов.
Можете не отвечать, я знаю почему. Это был скорее риторический вопрос, к вопросу о улучшении алгоритмов.
Сдаётся мне, операционки не «хомяки» пишут.С чего вы решили? Большая часть того, что сейчас понимается под словом «операционка» — как раз написано «миллионом сумасшедших хомячков».
И даже люди, которые могли бы сделать лучше не не делают этого, так как времени нет. Вплоть до того, что некоторые модули оказывают буквально в 30-50 раз больше и требуют во столько же раз больше ресурсов, чем могли бы!
15 лет назад стандартное разрешение экрана составляло 1024*768 точек при 16 бит цвете (1 572 864 байт).
Сейчас 1920*1080*32 бит (8 294 400 байт), уже это дает практически порядок в объеме данных для обработки, хотя частота функционирования процессоров увеличилась разве что в 2-4 раза.
Помимо этого сейчас мало кто пишет на низком уровне, всем подавай готовые модули и библиотеки для ускорения написания программ что не особо сказывается на производительности.
Сейчас 1920*1080*32 бит (8 294 400 байт), уже это дает практически порядок в объеме данных для обработки, хотя частота функционирования процессоров увеличилась разве что в 2-4 раза.
Помимо этого сейчас мало кто пишет на низком уровне, всем подавай готовые модули и библиотеки для ускорения написания программ что не особо сказывается на производительности.
Как связан объем фреймбуфера с частотой процессоров?
А как связана грузоподъёмность автомобиля с мощностью его движка?
Кнопку/команду «сделать красиво сейчас» еще не разработали, поэтому не смотря на часть автоматизации, процессору приходится напрягаться все сильнее.
Можно узнать какие именно «ресурсы» уходят «в песок» на 99%? Ну, хотя бы на 90?
Программа оптимизируется под аппаратные возможности, для оптимизации скорости вычислений. Кто-бы что не говорил про «зачем», могу в защиту своей идеи сказать следующее: данный подход позволит максимально эффективно использовать временной параметр «смена строк».
Сейчас доступ к памяти оптимизирован для последовательного обращения, как только начинаются ветвления и прыжки по памяти, так сразу начинаются задержки в предоставлении данных, для чего кстати и внедрили «hyper threading» в процессоры, пока 1 набор регистров ждет память, во 2 набор данные уже прибыли ранее.
Сейчас доступ к памяти оптимизирован для последовательного обращения, как только начинаются ветвления и прыжки по памяти, так сразу начинаются задержки в предоставлении данных, для чего кстати и внедрили «hyper threading» в процессоры, пока 1 набор регистров ждет память, во 2 набор данные уже прибыли ранее.
Sign up to leave a comment.
Быстродействие динамической оперативной памяти и нелепая идея как ее увеличить