[sigmaN 0]

Приветствую!

Господа, оцените пожалуйста мою не рекурсивную реализацию сортировки слиянием.
Покритикуйте, оцените ))  Чисто спортивный интерес. Прочитал описание алгоритма, запилил с нуля ради разминки мозга.

Основная "фишка" в том, что в отличие от рекурсивной реализации требуется меньше памяти как по объему так и по кол-ву выделений.
Один раз происходит выделение временного массива, равного по размеру исходному,  далее массивы переключаются по очереди и происходит слияние групп из одного в другой. Размер группы увеличивается в два раза за проход внешнего цикла.

В общем то всё то-же самое, что и в рекурсивной реализации, только немного быстрее и экономнее по памяти.

P.S. ясно, что рекурсивную реализацию в принципе тоже можно докрутить до однократного выделения памяти и работы уже из неё, но речь не о том.

void merge(int* dst, int dstSize, int* left, int leftSize, int* right, int rightSize)
{
	int leftIdx = 0;
	int rightIdx = 0;
	
	//printf("merge(dstsize=%i, leftsize=%i, rightSize=%i)\n", dstSize, leftSize, rightSize);

	for (int i = 0; (i < dstSize) && ((rightSize - rightIdx > 0) || (leftSize - leftIdx > 0)); i++)
	{
		//left array was exhausted, merge from right
		if (leftSize - leftIdx == 0)
		{					
				dst[i] = right[rightIdx];
				rightIdx++;							
		}
		//right array was exhausted, merge from left
		else if (rightSize - rightIdx == 0)
		{			
				dst[i] = left[leftIdx];
				leftIdx++;		
		}
		//both left and right still have elements to merge
		else 
		{			
			if (left[leftIdx] < right[rightIdx])
			{
				dst[i] = left[leftIdx];
				leftIdx++;
			}
			else
			{
				dst[i] = right[rightIdx];
				rightIdx++;
			}
		}						
	}
}

void mergeSortNonRecursive(int *a, int arrSize)
{
	int *a2;
	try {
		a2 = new int[arrSize];
	}
	catch (const std::bad_alloc& e) {
		printf("Bad alloc in mergeSortNonRecursive(): %s", e.what());
		return;
	}

	int *arrays[2] = { a, a2 };
	int arrayIdx = 0;
	int nextArrayIdx = (arrayIdx + 1) % 2;

	int groupLen = 2;

	int leftOffset;
	int leftSize;
	int rightOffset;
	int rightSize;
	int destOffset;
	int destSize;	

	do{
		leftOffset = 0;
		leftSize = 0;
		rightOffset = 0;
		rightSize = 0;
		destOffset = 0;
		destSize = 0;
		
		for (int i = 0; i < arrSize; i += groupLen)
		{
			destOffset = i;
			leftOffset = i;
			
			leftSize = arrSize - i;
			if (leftSize > groupLen / 2 )
				leftSize = groupLen / 2;
			
			rightOffset = leftOffset + leftSize;
			rightSize = groupLen - leftSize;
			if (rightOffset > arrSize - 1)			
				rightSize = 0;			
			else if (rightOffset + rightSize > arrSize - 1)
				rightSize = arrSize - rightOffset;

			destSize = leftSize + rightSize;
			//printf("destOffset=%i, leftOffset=%i, rightOffset=%i\n", destOffset, leftOffset, rightOffset);
			merge(arrays[nextArrayIdx] + destOffset, destSize, arrays[arrayIdx] + leftOffset, leftSize, arrays[arrayIdx] + rightOffset, rightSize);
		}

		arrayIdx = nextArrayIdx;
		nextArrayIdx = (arrayIdx + 1) % 2;
		groupLen = groupLen * 2;
	} while (groupLen <= arrSize);
	
	//doing final merge	if needed
	if (destSize != arrSize)
	{	
		//printf("doing final merge\n");
		rightSize = destSize;
		rightOffset = arrSize - rightSize;
		leftOffset = 0;
		leftSize = arrSize - rightSize;	
		destOffset = 0;
		destSize = arrSize;		
		merge(arrays[nextArrayIdx] + destOffset, destSize, arrays[arrayIdx] + leftOffset, leftSize, arrays[arrayIdx] + rightOffset, rightSize);
		
		arrayIdx = nextArrayIdx;
		nextArrayIdx = (arrayIdx + 1) % 2;
	}

	//copy result to a[] if it is not already there
	if (arrayIdx != 0)
	{
		for (int i = 0; i < arrSize; i++)
			a[i] = arrays[arrayIdx][i];
	}

	delete[] a2;
}

 

[iiv 16]

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

[sigmaN 0]

Quote

то лучше рекуррентно переключая вспомогательный массив

Не понял вашей идеи. Можно подробнее об этом?

[andrey_p 0]

Кэш практически убил классическую алгоритмическую оптимизацию. Существуют различные техники оптимизации программ и эти техники зависят от конкретного железа. Самое узкое место систем с динамической памятью - это подсистема памяти, включая кэши. Ядра молотят с огромной скоростью, проблема эффективно доставить данные к ядрам и "выгрузить" данные после обработки. Именно это является причиной прогресса в скорости обработки потоковых данных и практически полное отсутствие прогресса в скорости работы "алгоритмических" программ. Посмотрите на скорость работы графических ускорителей и на характер обрабатываемых ими данных, сразу станет всё понятно.

Если Вам интересна эта тема, найдите книгу Криса Касперски "Техника оптимизации программ". Несмотря на то, что книга устарела, её можно использовать как трамплин в мир оптимизаций. Есть неплохие курсы по оптимизации на зарубежных ресурсах, правда, на английском. Этот мир реально интересный. Познав подсистему памяти, Вы измените свой взгляд на классические алгоритмы:) И уж тем более забудете про динамическое выделение памяти там, где этого можно избежать. Ресурсов съедается немерено, да и фрагментацию никто не отменял.

Изменено 11 ноября, 2019 пользователем andrey_p

[iiv 16]

На пальцах, пока у вас сортировка идет с блоком размера 16кбайт (если мы про интелы) то надо считать число операций, а как только вы вылезли из этих пределов и пока еще линейно адресируетесь по памяти, число чтений и записи в эту память. Операции идут грубо говоря на тактовой процессора (вы всяко быстро не научитесь конвейеризовать инструкции) а обращение к памяти на ее тактовой, которая в 10 раз меньше. Ну а как полезете дальше в детали, то узнаете что кешей есть много и есть страничная организация памяти и есть векторно конвейерный параллелизм исполнения инструкций.

При старании сортировка может быть ускорена раз в 5 с учетом всего этого, но алгоритмы сортировки маленьких и больших массивов сильно отличаются

[sigmaN 0]

20 hours ago, andrey_p said:

Кэш практически убил классическую алгоритмическую оптимизацию.

Сильное заявление...

20 hours ago, andrey_p said:

Существуют различные техники оптимизации программ и эти техники зависят от конкретного железа.

На сколько мне известно, они обычно применяются после того, как выбран наиболее быстрый(в классическом понимании этого слова) алгоритм.

20 hours ago, andrey_p said:

Если Вам интересна эта тема, найдите книгу Криса Касперски "Техника оптимизации программ". Несмотря на то, что книга устарела, её можно использовать как трамплин в мир оптимизаций.

Почитаю,посмотрю. Но общее представление о работе подсистемы памяти у меня есть. Я даже несколько лекций Александреску смотрел в оригинале. Где про высоконагруженные системы и про то, что бесконечный цикл лучше цикла с условием, сравнивать лучше с нулем, не располагать bool в структурах, которые должны быть горячими в кэше  и так далее...

20 hours ago, andrey_p said:

И уж тем более забудете про динамическое выделение памяти там, где этого можно избежать. Ресурсов съедается немерено, да и фрагментацию никто не отменял. 

О том, что выделение памяти это дорого мы в курсе. Если бы функция сортировки вызывалась в программе достаточно часто, а максимально возможный размер массива был бы заранее известен то я бы выделил память один раз и вертел всё там.
 

19 hours ago, iiv said:

На пальцах, пока у вас сортировка идет с блоком размера 16кбайт (если мы про интелы) то надо считать число операций, а как только вы вылезли из этих пределов и пока еще линейно адресируетесь по памяти, число чтений и записи в эту память. Операции идут грубо говоря на тактовой процессора (вы всяко быстро не научитесь конвейеризовать инструкции) а обращение к памяти на ее тактовой, которая в 10 раз меньше.

Пока что не ясно как применить всё вышесказанное к алгоритму сортировки слиянием, который я реализовал выше.  Пока что мне кажется, что по памяти я всегда хожу линейно. Читаю всегда из одного массива - пишу в другой. Кэшу и блоку предсказаний процессора все карты в руки - пусть грузит в кеш память наперед, как только сообразит, что как минимум по чтению я по памяти всегда иду линейно от меньших адресов к старшим.

Ну наверно можно было бы двигаться на одном проходе на повышение адресов, а на другом проходе на понижение. Из соображений, что недавно записанные данные по стершим адресам сейчас "горячие" и двигаясь обратно от них мы попадем в кеш.

Или я как-то неправильно мыслю?

[iiv 16]

У вас алгоритм N log N операций сравнения и столько же операций по чтению и записи по памяти. Следовательно, помня, что память в десятки раз медленнее про сравнения пока забьем.

1 hour ago, sigmaN said:

Пока что мне кажется, что по памяти я всегда хожу линейно. Читаю всегда из одного массива - пишу в другой.

вот тут вы путаете операцию prefetch с доступом в кеш. Если бы у вас было бы куча вычислительной работы на одно чтение из памяти,  да, этот prefetch очень бы помогал, но у вас он как мертвому припарка.

 

Теперь давайте рассмотрим массив 1024 чисел 4 байтовых целых для сортировки, тогда вам надобно еще столько же памяти для временного буфера и тогда все это хозяйство влезает в 8кбайт, что меньше размера первого кеша. Пока у вас массив такой маленький, за первый проход вы его медленно зачитаете из памяти в кеш за N операций, а потом оставшиеся 9N операций (log 1024 - 1)*N будете обращаться только в кеш, то есть реально потратите времени как если бы 2N раз читали из памяти.

 

Если вы попарно, по 4, по 8 начнете гулять по всему огромному массиву, который не влез в кеш, то вы вместо этих 2N потратите 10N. То есть при длине в 1М ваш алгоритм должен потратить времени, примерно равному чтению 20M ячеек памяти, а полностью рекурентный - только 12M.

 

Если хочется оптимизировать дальше, то можно обойтись всего-то 4M, что по сравнению с 20M даст выигрыш в 5 раз. Вроде не много, но тоже что-то. Вот если бы большие матрицы друг на друга умножали бы, там можно было бы получить выигрыш и в 100 раз. Я еще 20 лет назад своим студентам лекции по вычислительной математике начинал с примера умножения матриц, просил их написать, а демонстрировал хорошо оптимизированный по кешу и конвейеру алгоритм, который обыгрывал их реализацию в 10-100 раз (раньше отношение пиковой производительности к доступу к памяти было не такое большое), после этого студентам было интересно ходить ко мне на лекции. Почитайте книжку, что вам посоветовали, или просто погуглите про процессорные кеши и кеш оптимизацию математических алгоритмов - узнаете много нового. В настоящий момент программную реализацию (после вывода теоретических формул) начинают не с программирования, а с планирования как распределить память под задачу на той архитектуре, на которой планируется считаться. Понятно, AVR и аналогичных процессоров с детерминистическим доступам это не касается :)

[andrey_p 0]

2 hours ago, sigmaN said:

Сильное заявление...

Есть богатый опыт оптимизации и разработки высоконагруженых приложений.

 

2 hours ago, sigmaN said:

На сколько мне известно, они обычно применяются после того, как выбран наиболее быстрый(в классическом понимании этого слова) алгоритм.

Увы, но это давно не так. Оптимальный код узких мест разрабатывается с учётом специфики платформы. Этот код хорошо документируется, так как при смене платформы он модифицируется или переписывается под новую платформу.

 

2 hours ago, sigmaN said:

Кэшу и блоку предсказаний процессора все карты в руки - пусть грузит в кеш память наперед, как только сообразит

Да он нормально не сообразит без подсказок. Для правильной оптимизации нужно понимать архитектуру кэша в целом и на каждом уровне (N-way associative / direct mapped), понимать алгоритмы (политики) вытеснения данных из кэша, алгоритмы синхронизации ядерных кэшей, алгоритмы подсветки страниц памяти, принцип работы TLB и т.п.

 

 

5 minutes ago, iiv said:

после этого студентам было интересно ходить ко мне на лекции

Вашим студентам несказанно повезло, сейчас мало кто этим озадачивается.

 

 

5 minutes ago, iiv said:

В настоящий момент программную реализацию (после вывода теоретических формул) начинают не с программирования, а с планирования как распределить память под задачу на той архитектуре, на которой планируется считаться.

И за это Вам огромное спасибо! Я думал, что этому сейчас и не учат...

 

 

 

Изменено 12 ноября, 2019 пользователем andrey_p

[sigmaN 0]

Спасибо, интересно, задумался...

 

[sigmaN 0]

Были проведены измерения на массиве 100'000'000 элементов. Размер примерно 400 мегабайт.

Для более консистентных результатов new был заменен на временный массив(static глобальная переменная, такая-же, как и сортируемый массив).
Перед сортировкой массив заполняется отсортированной в обратном порядке последовательностью. Время выполнения измерялось через QueryPerformanceCounter() перед и после вызова функции сортровки.

i7-2630QM DDR3-1333 dual channel, Visual Studio 2013 флаги компилятора /Ox /Ot /Oy

Исходная реализация(код в первом посте, new заменен на статический временный массив).
Array = 100000000 elements, sizeof() = 400000000
Timer = 8241447us (8.241448sec)

Модифицированная реализация быстрее на 43%:
Array = 100000000 elements, sizeof() = 400000000
Timer = 4759489us (4.759489sec)

Модификации подверглась только функция merge(), её новая реализация под спойлером. Если кратко, то разные условные переходы были по максимуму вынесены из цикла.

Spoiler

 

void merge(int* dst, int dstSize, int* left, int leftSize, int* right, int rightSize)
{
	int leftIdx = 0;
	int rightIdx = 0;

	//printf("merge(dstsize=%i, leftsize=%i, rightSize=%i)\n", dstSize, leftSize, rightSize);
	if ( (leftSize == rightSize) && (rightSize == dstSize) )
	{		
		for (int i = 0; i < dstSize; ++i)
		{
			if (left[leftIdx] < right[rightIdx])
			{
				dst[i] = left[leftIdx];
				++leftIdx;
			}
			else
			{
				dst[i] = right[rightIdx];
				++rightIdx;
			}
		}
	}
	else
	{
		int mergeUntil = min(leftSize, rightSize);
		int i;
		for (i = 0; i < mergeUntil; ++i)
		{
			if (left[leftIdx] < right[rightIdx])
			{
				dst[i] = left[leftIdx];
				++leftIdx;
			}
			else
			{
				dst[i] = right[rightIdx];
				++rightIdx;
			}
		}
				
		if (leftSize - leftIdx == 0) //left array was exhausted, merge from right
		{
			for (; i < dstSize; ++i)
			{
				dst[i] = right[rightIdx];
				++rightIdx;
			}
		}		
		else if (rightSize - rightIdx == 0) //right array was exhausted, merge from left
		{
			for (; i < dstSize; ++i)
			{
				dst[i] = left[leftIdx];
				++leftIdx;
			}
		}
	}
	
}

Из полученных результатов я сделал вывод, что узким местом была не память, а процессор.
Хотя изначально казалось, что т.к. между доступами к памяти нет никаких особых вычислений то упрёмся мы в любом случае в память и несколько if() туда-сюда "погоды не сделают". Это оказалось не так.

On 11/11/2019 at 10:06 PM, iiv said:

На пальцах, пока у вас сортировка идет с блоком размера 16кбайт (если мы про интелы) то надо считать число операций, а как только вы вылезли из этих пределов и пока еще линейно адресируетесь по памяти, число чтений и записи в эту память. Операции идут грубо говоря на тактовой процессора (вы всяко быстро не научитесь конвейеризовать инструкции) а обращение к памяти на ее тактовой, которая в 10 раз меньше.

Продолжу исследовать эту тему.
Пока что посмотрел эти два видео

https://youtu.be/Nsf2_Au6KxU

https://youtu.be/WDIkqP4JbkE

Потом еще раз почитал PDF со слайдами Scott Meyers: Cpu Caches and Why You Care https://www.aristeia.com/TalkNotes/codedive-CPUCachesHandouts.pdf

[iiv 16]

51 minutes ago, sigmaN said:

Array = 100000000 elements, sizeof() = 400000000

Timer = 4759489us (4.759489sec) 

для выполнения сортировки массива 100М, вам надобно 1.4Г сравнения, или, если в лоб, 28* 400*2=22.4ГБ передачи данных по памяти. Если считать, что за 4.75 Ваш процессор выполнит 19 Г сравнений, или начитает/напишет 50ГБайт из памяти, очевидно, что Вы сортировали упираясь на доступ в память, DDR3-1333 имеет скорость около 11ГБайт/с, чуток задействовав кеш на первых коротких сортировках.

 

То есть при должном старании вы должны получить эту сортировку за 1.2 секунд (5ГБайт передач по 11ГБ/с впараллель с 19Г операций по 16Г в секунду, 8 сравнений за такт i7, если мне не изменяет память) и только тогда оно сядет на скорости процессора, и это вместо ваших 4.75 секунд.

 

Теперь надо еще вспомнить, что есть кеш инструкций (L1 тоже 16кбайт, про остальные кеши не стоит думать), есть еще плохая конвейеризация инструкций (сброс предсказателя загрузки очередной команды) при выполнении условных переходов и с этими факторами тоже надо бороться - они могут полностью перечеркнуть все ваши старания.

[sigmaN 0]

Или я вас не понял или вы сделали неправильный вывод из расчетов.
Я мыслю так:
Внутренний цикл сорта в итоге копирует весь массив, посредством вызова merge() нужное кол-во раз.

Давайте упростим и забудем про сравнения. Нам 381.4МБ через шину памяти надо протолкнуть 28 раз, умножаем на 2, потому как чтение+запись. Итого 28*381,4*2 = 20,8ГБ.

Вы утверждаете, что DDR3-1333 может около 11ГБайт/с. Таким образом, если бы мы сидели на памяти, то потребовалось бы 20,8 / 11 = 1,89сек.

О том, что сейчас мы сидим на процессоре, а не на пропускной способности памяти говорит и тот факт, что изначально потребовалось 8 секунд, а правка merge() касающаяся только кол-ва условных переходов в цикле, дала ускорение до 4.75сек.
При этом ни кол-во обращений к памяти ни размеры прокачиваемых через неё данных не изменилось, поскольку алгоритм сортировки не менялся и изменен быть не может (иначе это уже будет реализация не merge sort, а чего-то другого).

Считаю, что только после того, как процессор сможет всё сделать за 1,89сек мы упремся в память и как бы я не оптимизировал код - ускорения наблюдаться не будет. Т.к. пропускная способность памяти действительно закончится, а требование переслать туда-сюда нужное кол-во байт никуда не исчезнет (см. выше про то, что это всё-таки merge sort и он должен им оставаться).

 

Правильно ли я рассуждаю?

[xvr 12]

19 hours ago, sigmaN said:

Были проведены измерения на массиве 100'000'000 элементов. Размер примерно 400 мегабайт.

Если не трудно, сравните со стандартным std::sort. Пока ваши цифры больше напоминают 'лошадь в ваккуме' - без сравнения с другими реализациями сложно сказать хорошие они или нет. (Ещё бы было неплохо сравнить и разные компиляторы, как минимум gcc ну и Intel)

 

[sigmaN 0]

3 hours ago, xvr said:

сравните со стандартным std::sort

Сравнение сделаю.
Скорее всего там реализована не merge sort, а quick sort. За merge sort вроде как нужно идти к std::stable_sort но и то без гарантий, как мы понимаем.
https://stackoverflow.com/questions/5038895/does-stdsort-implement-quicksort

Студию обновил до 2019.

Вообще лично мне больше хотелось не просто поставить рекорды скорости, а именно разобраться что к чему с кешами и так далее, в плане оптимизации быстродействия.
Вот, добился ускорения, измерил.  Можно воспринимать эти цифры как относительные измерения, не абсолютные )

 

Add:

std::stable_sort(arr, arr + N);   
Array = 100000000 elements, sizeof() = 400000000
Timer = 3911853us (3.911853sec)

 

std::sort(arr, arr + N);

Array = 100000000 elements, sizeof() = 400000000
Timer = 2681706us (2.681706sec)

 

Add2: беглое чтение реализации stable_sort показало, что merge sort там используется. Правда через несколько условий которые я не проверял. Для маленьких массивов меньше 32 элемента используется insertion sort для остальных разные варианты merge sort в зависимости от доступности временного буфера.  Почитаю там потом внимательнее что происходит у них. Пока интересно самому по-оптимизировать, а не копировать подсмотренные решения.

 

Add3: сравнение компиляторов студии 2013 и 2019 различий в скорости моей реализации не показало.

[xvr 12]

Т.е. ваша реализация в 2 раза медленнеё стандартного quicksort'а. Тогда зачем она?

19 hours ago, sigmaN said:

Вообще лично мне больше хотелось не просто поставить рекорды скорости, а именно разобраться что к чему с кешами и так далее, в плане оптимизации быстродействия.

Для этого лучше изучать перемножение матриц (больших). Там кэши встают в полный рост.