Хочу написать сверхбыстрый сортировщик словарей без ограничения размера. Погуглил, нашёл что в Visual Studio 2010 есть MASM 64, но учитывая отсутсвие инфы на русском по нему, считаю что язык высокого уровня будет предпочтительней. Задача - сортировать гигабайтные словари в памяти за малое время стандартными алгоритмами (пузырёк, расстановка индексов, попарное слияние и т.д.).
Я се визуал 2008 установил потестил немного - потом буду изучать досконально. А так - норма думаю КАКОЙ МАСМ 64 бит для словорей
Язык - любой компилируемый, который позволяет создавать приложения под 64 битную систему. Здесь, скорее, нужно о алгоритме работы беспокоится.
Ну это и ежу понятно, про это и спрашиваю... Алгоритм есть, вопрос в снятии ограничения памяти в 2 Гб. в win32.
Да не, просто за 1 раз много можно сразу в памяти сортировать в случае 64-х битного приложения. Куча процесссов толкающихся в 2 Гб. памяти - не выход. Там обход ограничения только сортировка блоками с последующим слиянием попарно. http://ru.wikipedia.org/wiki/Сортировка_слиянием
Если хочешь писать сверхбыстрый то смотри не в сторону процессора, а видеокарты. http://ru.wikipedia.org/wiki/CUDA И на паралельные способы сортировки, аля http://en.wikipedia.org/wiki/Bitonic_sorter
Ну почему же, в оперативной памяти сортировку можно осуществить давольно быстро тем или иным алгоритмом, было бы её достаточно. Память современных видеокарт обычно ограничена 2Гб. (реже 3 и 4Гб). Что так же накладывает ограничение на размер словаря подвергающемуся сортировке. к примеру 1Гб Nvidia Cuda тянет всего 70 млн. хэшей md5. Да и к чему тут использование параллельных вычислений, если речь лишь о перестановке (расстановке индексов?). P.S. Современные же материнки поддерживают 32Гб. памяти и более, да и сама оперативная (DDRIII) память сейчас дёшева как никогда. P.P.S. Т.е. главная идея все перестановки совершать в памяти без каких либо промежуточных операций с диском, поэтому и смотрю в сторону 64-битного софта.
Блин я тебя не доганяю. Смотри у тебя есть несколько гигабайт данных в формате md5 : пароль и тебе их нужно расставить по возрастанию, так? Если да, то берешь С++, создаешь огромный массив, читаешь туда данные и сортируешь, никаких обращений к диску не будет. "Да и к чему тут использование параллельных вычислений" При том, что сортирует у тебя процессор, и если ты будешь писать просто, то сортировать будет только одно ядро.
Сколько памяти будет выделено? Не более 2Гб. в win32 весь массив не уместится в памяти - поэтому обращения к диску (файл подкачки) не избежны, что сильно тормознёт сортировку. Да мне и одного ядра хватит для пересылок данных в памяти.
попробуй написать сначала 32-битный сортировщик с ТЗ отсортировать один гигабайт. И затем сделай еще одну его версию, котрая будет использовать 100мб ОЗУ и 900Мб дискового кэша. Это позволит тебе обнаружить зависимость скорости сортировки от фактора, который ты не учел ранее - размера кэша процессора. Сортировка в памяти 500Мб массива занимает, грубо, раз в 15 дольше, чем сортировка 15-ти 33Мб массивов. А 5Гб массив будет в памяти сортироваться раз в 100 дольше, чем такой же массив, предварительно разбитый на 30-40Мб блоки. В идеале размер блока, подаваемого на вход алгоритма сортировки не должен превышать процессорного кэша, для того, чтобы в процессе сортировки все перемещения элементов в массиве происходили внутри процессорного кэша, а не ОЗУ. По большому счёту само количество ОЗУ при сортировке роли то почти и не играет, т.к. в ней не целесообразно собственно сортировать. И следовательно, данные, которые ты поместишь в ОЗУ твоей программе будет суждено будет считать от силы несколько раз. Да, каждое из таких считываний - экономия времени. Но даже для огромного, 100-гигабайтнгого словаря тебе не удастся сэкономить больше, чем время 7-8 считываний-записей 100Гб на жесткий диск. И хотя это - тоже много, но в любом случае даст прирост лишь в десятки процентов по сравнению с вариантом, в котором ты стал бы использовать в приделах 100 Мб озу. Тем более что 100 гигов оперативы у тебя всё равно скорее всего не будет, а прирост при использовании 24 гб будет куда меньше - и всё равно придется кэшировать. Но начинание у тебя хорошее.
-=lebed=-, Я думаю Mergesort, о котором ты упомянул выше, в твоем случае будет оптимальным вариантом. Для такого обьёма файлов без разделение на блоки и подблоки никак. Ты вообще читал посты выши или просто решил, что нибудь сказать?
(o.0) чукча не читатель, чукча писатель. Хотя я видимо я и правда написал не достаточно понятно. Мержсорт не требует много памяти, это факт. Но он совершает адову кучу операций чтения из озу на третьем этапе, особенно когда объединяемые массивы уже не по несколько сотен байт, а по паре сотен мегабайт. Чтение из озу быстрее, чем с винта. В сотни раз. И раз в сто медленнее, чем из кэша проца. Но в кэше много не уместить, и следовательно "причем тут кэш?". Все верно, не при чем. И именно поэтому, для эффективной сортировки - побдобно тому как лебедь пытается "уйти" от медленного винта, он, так же как и ты, Spot, должны думать о том, как максимально уйти еще и от медленной (по сравнению с кэшем процессора) оперативки. Как? Нужно стараться совершать пусть и максимум операций, но в минимуме памяти. На поздних этапах сортировки слиянием, когда алгоритм будет сливать в один два, скажем, 40а-мегабайтных массива, затем два по 80Мб и так далее - все эти слияния будет происходить хотя и "сравнительно" быстро, но гораздо медленнее, чем могли бы. Проц в этом случае вынужден будет по многу раз (при слиянии 2х10мб, 2х20, 2х40 итд) обращаться к одним и тем же значениям, находящимся в озу. Для достижения же максимальной скорости нужно сделать так, чтобы многократные обращения происходили к тем значениям, которые находятся в кэше (т.е. нужно стараться вновь менять местами те значения, которые уже менялись местами "недавно" и по прежнему находятся в кэше), многократные же обращения к одним и тем же значениям вне кэша нужно стараться минимизировать. В общем, я не уверен, что хотя бы в этот раз написал достаточно понятно. Но если и снова кто-нибудь не поймет - скажу еще проще. В компе есть нет два типа памяти, разница в скорости между которыми составляет 1000(ram)_к_1(hdd). В компе есть три типа памяти, и их соотношение, грубо говоря(у кэшей разного уровня скорость доступа разная, но нам интересны L2 и L3): 100.000(cpu cash)_к_1000(ram)_к_1(hdd). Не забывайте об этом. Иначе даже без использования файла подкачки будующий мега-сорт не сможет обойти по скорости уже существующий софт. как-то так.)
Начали с языка договорились до архитектуры) Думаю тут нужен эмпирический подход. Теория с практикой только в теории совпадает.
я как раз и начинал с того, что лебедю надо самому попробовать написать сортер хотя бы на 1 гиг, чтобы понять что и как. И не строить глобальных планов насчет облачных вычислений, гпу, 64 бит, и покупки компа с 32гб озу специально для сортировки словарей, а вместо этого брать самый обычный С++, учебник по нему, и садиться писать. Для самых обычных 32 бит, и да, с ограничением в 2 гига ОЗУ. Для начала - на чистом с++, затем, если захочется, код алгортитма сортировки можно будет заменить на аналогичную ассемблерную вставку. Ну а затем уж, если ради прироста скорости сортировки на 30-40 процентов захочется переписать под 64 бита и купить мать с 32Гб озу, ну значит так тому и быть. Но т.к у большинства пока ещё, наверное, 32битные системы, да и на 64битных врятли у кого больше 8-12гб, то за 32-битную версию, которой для работы достаточно 2 гигов памяти, больше людей, мне кажется, сказали бы спасибо. Ну а насчет того, что под 32 бита сортеры уже есть - не важно. При правильном подходе вполне можно написать сортер мощнее всех существующих. Просто никому из серьезных программистов это никогда было не надо. Вон.. если бы слеш взялся.. был бы не только самый быстрый, но еще и самый компактный сортер в мире. Да еще и, небось с веб-админкой, приёмом заданий через irc и заливом готовых пасслистов куда-нибудь по ftp А так - самый мощный сортер словарей вполне может стать от -=lebed=-
я нихера непонел. берется сипп студия10. берется configuration manager и добавляется таргет для х64 или itanium платформы. соотвтственно объектный код будет сгенерен под соответствующую платформу. что касается инлайна асма - то да, на х64 эта штука не поддерживается. можно разными путями пойти - добавить build customization под масм, либо по ходу build steps - хоть фасмом компилить, - в этих случаях просто не инлайн будет, а готовые объектные модули. можно и вообще шеллкодом. все от фантазии зависит. тащемта под х64 аж 8 терабайт юзермода доступно поидее (стокаж и у ядра) да и ширина шины всетаки не 32 а 64бита, так что должен эффективнее с памятью взаимодействовать. ну и чтобы не свапились твои массивы на диск из виртуалпамяти - лочишь в физ памяти через VirtualLock и работаешь
sn0w, асм можно юзать через Intrinsics. Конечно функционал чуть ограничен, но возможности почти теже. http://msdn.microsoft.com/en-us/library/26td21ds
slesh конечно можно, но если низкоуровневую функцию проще написать полностью на асме - то лучше это так и оформить в отдельном модуле. единственная разница - интринсики инлайнятся в код. Code: char testbyte = 77, shift = 2; 00411B85 mov byte ptr [ebp-0B1h],77 00411B8C mov byte ptr [ebp-0BDh],2 testbyte = _rotr8(testbyte, shift); rotr8 intrinsic 00411B93 mov cl,byte ptr [ebp-0BDh] 00411B99 mov al,byte ptr [ebp-0B1h] 00411B9F ror al,cl 00411BA1 mov byte ptr [ebp-0B1h],al а при линковке с masm/fasm/ итд объектниками придется таки делать call. с одной стороны - экономия места. но исчо, касаемо фасма, иногда приходится в самом листинге именовать функции в соответствии с требуемой декорацией для определенного вызова (fastcall stdcall cdecl) - _myfunc@8 или _myfunc чтобы с си сорца вызвать myfunc(a,b)
