64-бита, указатели и массивы

Итак, потихоньку переезжаю на 64-битный режим. Его преимущество очевидно - существенно больший, практически не ограниченный в обозримом будущем объем доступной оперативной памяти. Но есть и недостаток - размер указателей стал в 2 раза больше. 😀

Чем же это плохо? Плохо это становится, когда требуется интенсивная работа с указателями. Например, в случае двоичного дерева требуется на один узел хранить 2 указателя. Пусть в каждом узле мы храним 4-байтное целое.
Тогда на 32-битных системах полезная нагрузка будет всего лишь 33%, а вся остальная память уйдет на организацию структуры данных. При переходе на 64-разрядную систему полезной нагрузки будет всего лишь 16%, а основная часть памяти уйдет на структуру.

Казалось бы, какая разница? Ведь на 64-битных системах памяти, как говорится, хоть жопой жуй. Но это чисто теоретически. Практически же объем памяти в реальных системах ограничен как экономическими соображениями, так и техническими возможностями материнской платы. Мне кажется, в типичных настольных системах в настоящее время 16 ГиБ не часто встречается, а 32 ГиБ - очень редко. Поэтому если вам не хватало памяти в 32-битном режиме, не факт, что при переходе в 64-битный ее в реальности будет так много, что вообще не нужно будет думать об экономии.
Но основная причина все же не нехватка памяти из-за размера указателей, а снижение скорости работы, так как по шине данных нужно передавать в 2 раза больше данных, плюс снижается эффективность работы кэша. Допустим, у нас была 32-битная система с частотой памяти 1600 МГц, ее портировали на 64-битную и запустили на новой системе с частотой памяти 3200 МГц. И в результате (если в системе используется интенсивная работа с указателями), получили такую же производительность, как и на старой системе!

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

Ладно, вернемся к нашим баранам, то есть к тестированию производительности. Казалось бы, где там указатели, когда СЛАУ задается матрицей? Давайте посмотрим.
Набор матриц для СЛАУ можно описать разными способами. Самый простой:

TMatrices = array[1..k] of array[1..n] of array[1..n+1] of single;

Здесь для понятности массив индексируется с 1, хотя с 0 эффективнее. Впрочем, возможно, компилятор оптимизирует все это дело, но не факт. Здесь k - количество систем, n - размерность СЛАУ. Последний индекс на единицу больше, так как свободные члены СЛАУ хранятся просто в последнем столбце.
Кроме простоты, ничего хорошего в данном варианте нет. Главный недостаток - количество систем и их размер нужно знать заранее, до компиляции программы. От этого недостатка легко избавиться, просто перейдя к одномерному массиву:

TMatrices = array[0..Size-1] of single;

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

m[q, i, j]

а дальше компилятор сам сделает всю работы, то во втором случае придется чуть усложнить:

m[q*n*(n+1) + i*(n+1) + j]

С точки зрения вычислительной сложности оба варианта эквивалентны, по крайней мере для оптимизирующего компилятора. Во втором случае у нас появляется указатель, так как память выделяется динамически по мере необходимости, но он всего лишь один и никакой интенсивной работы с ним нет.
Но у обоих вариантов есть еще один недостаток: при решение СДАУ методом Гаусса-Жордана для снижения ошибки решения необходимо выделять главный элемент, что требует обмена строк, а это,  в общем-то, является очень медленной операцией.
Для решения проблемы можно было бы воспользоваться динамическими массивами, тогда объявление типа выглядело бы так:

TMatrices = array of array of array of single;

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

TRow = array[0..65535] of single;
PRow = ^TRow;
TMatrix = array[0..65535] of PRow;
PMatrix = ^TMatrix;
TMatrices = array[0..65535] of PMatrix;
PMatrices = ^TMatrices;

Примерно, потому как в реальности система типов у меня чуть посложнее, но здесь приводить ее не стал, что бы не загромождать.
В данном случае, после выделений памяти, обращаться к ячейкам СЛАУ можно также просто, как и в самом первом случае, а обмен строк целиком заменяется очень быстрым обменом указателей.
И именно в этом варианте, как видно, появляется целых два массива указателей. Для больших размерностей это совершенно не критично, а вот для маленьких, возможно, будет иметь заметное значение в 64-битном режиме.

Поэтому попробую от указателей избавиться. Видится мне это пока примерно так:

TLESData = array[0..65535] of single;
PLESData = ^TLESData;
TLESRows = array[0..65535] of cardinal;
PLESRows = ^TLESRows;
TLESSet = array[0..65535] of PLESData;
PLESSet = ^TLESSets;

Здесь TLESData ‒ одномерный массив, как во втором, рассмотренном выше, варианте. Для того, что бы можно было быстро менять строки местами, используется тип TLESRows, в котором хранятся индексы первых элементов строк в массиве TLESData.
Так как в TLESRows хранятся 32-битные беззнаковые целые, он позволяет адресовать до 4 миллиардов (2³²) чисел в TLESData. Это позволит использовать до 16 ГиБ памяти под коэффициенты СЛАУ в случае FPU32, для других вещественных типов пропорционально больше. В случае СЛАУ из 3-х переменных это позволит хранить почти 358 млн. систем!
Адресация элементов матрицы, правда, в этом случае будет немного другой, чем во втором случае:

m[Rows[q*n + i] + j]

Мне кажется, такой вариант очень эффективно оптимизируется и будет быстрее, чем обращение просто по указателю.
Зачем же нужен третий тип, TLESSet? Дело в том, что производительность современных процессоров такова, что вполне вероятно топовые процессоры имеют или в ближайшем будущем будет иметь такую производительность, что смогут решить 358 млн. систем быстрее, чем за секунду! И уж тем более могут быть быстрее, когда речь идет про все ядра. И в таких случаях мне и потребуется несколько одномерных массивов по 16 ГиБ каждый в пределе, что бы можно было оттестировать такие монструозные процессоры.

Теперь остается попытаться реализовать все это на 64-битной версии Delphi. Прямо интересно, удастся ли это мне сделать или нет. В частности, на текущий момент та версия, что стоит у меня, даже в 64-битном режиме не позволяет создавать и обращаться к массивам размером больше 2 ГиБ. Естественно, на ассемблере эти ограничения мне нипочем, но не хотелось бы вообще все писать на нем. Впрочем, у меня есть идеи, как обойти это ограничение.
Хорошо хоть вроде бы память под динамические структуры выделяется полноценно. Но посмотрим.