Тяпничная huge-сортировка / Программирование

ReSQL.ru

Мобильная версия Контакт Правила FAQ Помощь

Гость

Войти | Регистрация | Профиль | Очистить

Новые сообщения | Избранное

Форумы | Пользователи | Статистика | Мод. лог | Поиск

Цитировать

Написать

Автор*:

Ввести пароль для входа

Тема*:

Сообщение

Данное сообщение тематическое

Сообщение содержит картинки или видео 18+

Автор:

ВНИМАНИЕ! На данном подфоруме действуют строгие правила. Удостоверьтесь, что ваше сообщение соответствует им!

Форум или тема закрыты для гостей. Необходима авторизация!

Загрузить последнюю сохраненную версию

Вложение:

Вставить как галерею

Максимальный размер вложений: 4,0 МБ, аудио/видео: 8,0 МБ. Картинки большего размера ужимаются, если возможно.

Введите код, изображенный на картинке. Если код нечитаемый, кликните картинку, чтобы загрузить другой вариант.

Отправляя сообщение, я выражаю свое согласие с правилами форума и принимаю пользовательское соглашение.

Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр

Форумы / Программирование [игнор отключен] [закрыт для гостей] / Тяпничная huge-сортировка

25 сообщений из 133, страница 4 из 6

все

Тяпничная huge-сортировка

#39418440

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

mayton, втянул все-таки в атаку на на сферических коней

Одно радует, у Леонида тоже не не взлетело 20289897
Leonid KudryavtsevСейчас код допишу и на SSD протестю.

...

Рейтинг:

0 / 0

13.03.2017, 20:39

| Ответить | Цитировать | Написать

Тяпничная huge-сортировка

#39418470

kealon(Ruslan)

Участник

Откуда: Нижневартовск

Сообщения: 4 020

Рейтинг: 0 / 0

Dima TНет оснований. По середине между прогой и HDD стоит ОС со своим кэшем и боле-мене выравнивает эту проблему.
10Гб очень скажем хорошо выравниватель ломает - ACID для файловой системы никто не отменял

...

Рейтинг:

0 / 0

13.03.2017, 21:32

| Ответить | Цитировать | Написать

Тяпничная huge-сортировка

#39418500

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Dima Tmayton, втянул все-таки в атаку на на сферических коней

Одно радует, у Леонида тоже не не взлетело 20289897
Leonid KudryavtsevСейчас код допишу и на SSD протестю.
Не втянул. А заинтересовал. :)

А я из-за чортовых акторов полез обновлять свой MinGw.

...

Рейтинг:

0 / 0

13.03.2017, 22:51

| Ответить | Цитировать | Написать

Тяпничная huge-сортировка

#39418504

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Dima TLeonid Kudryavtsevпропущено...

Разница скана в RAM и доступ к диску/ленте - не порядки, а несколько порядков (тысячи, десятки тысяч раз, а может и больше).
DDR4 - 4,5 Гб/сек, SSD - 0,5 Гб/сек всего в 9 раз, даже одного порядка не набирается.
Когда мы читаем файл или просто byte array последовательно (merge) с нулевого элемента
по последний - то работает одна магия. Эта магия обычно указана на коробке устройства
и она близка (с оговорками) к throughput.

Когда мы делаем random-access чтение или чтения в обатную сторону с обменом (quick-sort)
то может внезапно (!) так случится что включится другая магия и ваши предположения
о скорости доступа могут внезапно стать неверными. SSD - это не плоская матрица битов.
Это сложная структура со своими характеристиками. С гистерезисом (отклик нагрузки - не линейный
а изломаный). С гранулярностью (удобно читать не байты а какие-то порции покрупнее, секторы,
db_blocsk). С кешами (повторное чтение порций). На этом уровне обычно меряют IOP-s
для баз данных и их индексов.

Поэтому уж коли вы взялись за SSD - то давайте подойдем к ней как инженеры.
Возможно имеет смысл для начала ее отформатировать в Ext4 с соотв. опцией.

...

Рейтинг:

0 / 0

13.03.2017, 23:04

| Ответить | Цитировать | Написать

Тяпничная huge-сортировка

#39418574

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Посчитал статистику дерева триплетов. Вычитываю максимум последовательностей и запускаю их совместное слияние.

ПоследовательностейУровней дереваСравненийСтрок на выходе128711`822`3207332568111`952`766141251291`100`351`9552784
Файл похоже слабосортированный, средний размер последовательности 5.5 строк.

Слишком много сравнений. При двухкратном увеличении выборки десятикратное увеличение сравнений.

ИМХО Полноценную сортировку на триплетах не сделать. Поэтому нет смысла более 4-8 последовательностей сливать одновременно, а может и меньше, тут надо от скорости IO памяти и диска отталкиваться.

PS Надо std::sort подключать и акторы :)

...

Рейтинг:

0 / 0

14.03.2017, 08:15

| Ответить | Цитировать | Написать

Тяпничная huge-сортировка

#39418577

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Про random-read: он не случайный, а в основном последовательный. Запись только последовательная.

Алгоритм такой:
Последовательно читаем исходный файл запоминая координаты сортированных последовательностей, набираем N последовательностей, затем берем эти последовательности и сливаем, т.е. читаем последовательно но из разных мест файла. Как вариант можно не в одном файле указателем скакать, а открыть N раз файл. Не знаю как для ОС удобнее, возможно без разницы, т.к. там идет постраничное проецирование файла в кэш ОС, а дальше работа с кэшем.

После промежуточного слияния во временный файл он будет читаться полностью последовательно.

...

Рейтинг:

0 / 0

14.03.2017, 08:40

| Ответить | Цитировать | Написать

Тяпничная huge-сортировка

#39418655

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Dima TПосчитал статистику дерева триплетов.
Вот с этого момента я не понимаю. О какой структуре данных ты говоришь?

...

Рейтинг:

0 / 0

14.03.2017, 10:58

| Ответить | Цитировать | Написать

Тяпничная huge-сортировка

#39418670

д0kХ

Гость

maytonDima Tпропущено...

DDR4 - 4,5 Гб/сек, SSD - 0,5 Гб/сек всего в 9 раз, даже одного порядка не набирается.
Когда мы читаем файл или просто byte array последовательно (merge) с нулевого элемента
по последний - то работает одна магия. Эта магия обычно указана на коробке устройства
и она близка (с оговорками) к throughput.

Когда мы делаем random-access чтение или чтения в обатную сторону с обменом (quick-sort)
то может внезапно (!) так случится что включится другая магия и ваши предположения
о скорости доступа могут внезапно стать неверными. SSD - это не плоская матрица битов.
Это сложная структура со своими характеристиками. С гистерезисом (отклик нагрузки - не линейный
а изломаный). С гранулярностью (удобно читать не байты а какие-то порции покрупнее, секторы,
db_blocsk). С кешами (повторное чтение порций). На этом уровне обычно меряют IOP-s
для баз данных и их индексов.

Поэтому уж коли вы взялись за SSD - то давайте подойдем к ней как инженеры.
Возможно имеет смысл для начала ее отформатировать в Ext4 с соотв. опцией.

+ лайк.

...

Рейтинг:

0 / 0

14.03.2017, 11:09

| Ответить | Цитировать | Написать

Тяпничная huge-сортировка

#39418679

д0kХ

Гость

kealon(Ruslan)Dima TНет оснований. По середине между прогой и HDD стоит ОС со своим кэшем и боле-мене выравнивает эту проблему.
10Гб очень скажем хорошо выравниватель ломает - ACID для файловой системы никто не отменял

У файловой системы нет ACID.

Если болле точно, то ACID ФС распостраняется на один файл .
Если приложение работает с несколькими файлами , то никакая ФС
не гарантирует логическую консистентность файлов между собой.

...

Рейтинг:

0 / 0

14.03.2017, 11:15

| Ответить | Цитировать | Написать

Тяпничная huge-сортировка

#39418694

д0kХ

Гость

maytonDima TПосчитал статистику дерева триплетов.
Вот с этого момента я не понимаю. О какой структуре данных ты говоришь?

Афигеть :)

А ты какую структуру имел ввиду когда начинал топик ?

...

Рейтинг:

0 / 0

14.03.2017, 11:32

| Ответить | Цитировать | Написать

Тяпничная huge-сортировка

#39418705

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

д0kХmaytonпропущено...

Вот с этого момента я не понимаю. О какой структуре данных ты говоришь?

Афигеть :)

А ты какую структуру имел ввиду когда начинал топик ?
О дереве триплетов я не говорил.

Моя предлагаемая оптимизация "rolling-triplet" (крутящийся треугольник) касалась
вобщем-то стандартного алгоритма сортировки на диске слиянием который
вы все знаете.

Но я не хоче никого ограничивать. Welcome! Только кидайте ссылки на источники.

...

Рейтинг:

0 / 0

14.03.2017, 11:38

| Ответить | Цитировать | Написать

Тяпничная huge-сортировка

#39418730

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

maytonDima TПосчитал статистику дерева триплетов.
Вот с этого момента я не понимаю. О какой структуре данных ты говоришь?
О такой

Код: plaintext

1.
2.
3.

1234
\/\/
 \/
Выход

1234 это источники последовательностей, т.е. 4 упорядоченные последовательности выдающие элементы по возрастанию.

У каждой последовательности есть два метода:

Код: plaintext

1.
2.
3.
4.
5.

// Интерфейс источника последовательности
class source_t {
	virtual const item_t* front() {// Первый элемент в очереди, NULL если пусто
	
	virtual void pop() { // Извлечение следующего элемента

Приемник просто вычитывет инфу пока последовательность не опустеет.

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.

// Интерфейс приемника
class destination_t {
	// Установка источника
	void source_set(source_t*& src) {
		assert(src != NULL);
		// Запись всего что есть в источнике
		const item_t* i;
		while(i = src->front()) {
			write(i);
			src->pop();
		}
	}

\/ это триплет. На входе две последовательности, на выходе одна. Он проверяет front() входов, и отдает тот что меньше и делает для того входа pop()

PS Пока писал как работает понял где я накосячил в коде :)
Я в триплете коряво перегрузил front(), он каждый раз проходит все дерево, опрашивая нижестоящих.
Надо кэшировать в триплете ответы нижних, а не опрашивать нижние каждый раз.

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.

	// Первый элемент в очереди, NULL если пусто
	const item_t* front() override {
		if (src[1]->front() == NULL) {
			*next_src = src[0];
			idx = 0;
		} else if (src[0]->front() == NULL) {
			*next_src = src[1];
			idx = 1;
		} else if(*src[0]->front() < *src[1]->front()) { // Сравнение
			idx = 0;
		} else {
			idx = 1;
		}
		return src[idx]->front();
	}

PPS Вечером будут новые замеры.

...

Рейтинг:

0 / 0

14.03.2017, 11:54

| Ответить | Цитировать | Написать

Тяпничная huge-сортировка

#39418745

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Dima T, ок. Сорян. А-то я грешным делом подумал что ты решил использовать тернарные деревья.

...

Рейтинг:

0 / 0

14.03.2017, 12:04

| Ответить | Цитировать | Написать

Тяпничная huge-сортировка

#39419157

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Починил дерево, триплеты оправданы :)

4096 триплетов сортируют 23000 строк за 290`000 сравнений. Чтение из файла 2 раза на каждую строку.

Памяти занято всего:
триплеты 114`688 байт
источники 655`360 байт (в каждом кэш под одну строку 128 байт)

...

Рейтинг:

0 / 0

14.03.2017, 17:51

| Ответить | Цитировать | Написать

Тяпничная huge-сортировка

#39419171

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Может кто идею подкинет как сливать во временные файлы?

Заполнил я массив источников под завязку, но файл еще не весь пройден, надо что-то слить во временный файл.

Из характеристик есть только размер каждой последовательности. т.е. 4096 размеров.

Надо как-то за один-два прохода выбрать кандидатов на слив.

Пока думаю считать средний размер и все что меньше или равно сливать.

...

Рейтинг:

0 / 0

14.03.2017, 18:05

| Ответить | Цитировать | Написать

Тяпничная huge-сортировка

#39419231

д0kХ

Гость

Dima TМожет кто идею подкинет как сливать во временные файлы?

Заполнил я массив источников под завязку, но файл еще не весь пройден, надо что-то слить во временный файл.

Из характеристик есть только размер каждой последовательности. т.е. 4096 размеров.

Надо как-то за один-два прохода выбрать кандидатов на слив.

Пока думаю считать средний размер и все что меньше или равно сливать.

Акторами решаешь ?

откуда взялось число 4096 ?

...

Рейтинг:

0 / 0

14.03.2017, 19:00

| Ответить | Цитировать | Написать

Тяпничная huge-сортировка

#39419239

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

д0kХАкторами решаешь ?
Однопоточно. Файловый IO не распараллелишь. Черновик тут давал 20291151

д0kХоткуда взялось число 4096 ?
2^12 = 4096
Чтобы дерево триплетов строить проще было.

Код: plaintext

	triplet_t trp[SOURCE_MAX];

Основание 2048, все остальное 2047, один лишний, да и фиг с ним, зато с размером массива не надо заморачиваться.

...

Рейтинг:

0 / 0

14.03.2017, 19:08

| Ответить | Цитировать | Написать

Тяпничная huge-сортировка

#39419270

д0kХ

Гость

Dima Tд0kХАкторами решаешь ?
Однопоточно. Файловый IO не распараллелишь. Черновик тут давал 20291151

Это наверное в винде
в линуксе аж на расс, как 2 пальца

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

...

Рейтинг:

0 / 0

14.03.2017, 19:39

| Ответить | Цитировать | Написать

Тяпничная huge-сортировка

#39419290

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

д0kХЭто наверное в винде
в линуксе аж на расс, как 2 пальца
И в винде это есть, но шнурок к диску все равно один, я из этого исхожу, т.е. или читать или писать в один момент времени. Тормоз там.
Запись я размазываю по времени, т.е. пишется по чуть-чуть но постоянно, дальше пусть ОС оптимизирует.

Задача стояла минимум памяти, я вписался в 1 Мб стэка, поэтому магическое число 4096, а не 8192, 16384, 65536 и т.д.

Допишу, скорость IO посчитаю и тогда будет понятно надо ли что-то параллелить.

...

Рейтинг:

0 / 0

14.03.2017, 20:18

| Ответить | Цитировать | Написать

Тяпничная huge-сортировка

#39419296

Aleksandr Sharahov

Участник

Откуда: Москва

Сообщения: 2 167

Рейтинг: 0 / 0

Dima TМожет кто идею подкинет как сливать во временные файлы?

Заполнил я массив источников под завязку, но файл еще не весь пройден, надо что-то слить во временный файл.

Из характеристик есть только размер каждой последовательности. т.е. 4096 размеров.

Надо как-то за один-два прохода выбрать кандидатов на слив.

Пока думаю считать средний размер и все что меньше или равно сливать.

Совсем необязательно иметь такую кучу файлов.
По идее, можно обойтись количеством, равным количеству устройств.
Т.е. на каждом устройстве - один файл, состоящий из K отсортированных кусков по N записей.

...

Рейтинг:

0 / 0

14.03.2017, 20:26

| Ответить | Цитировать | Написать

Тяпничная huge-сортировка

#39419309

д0kХ

Гость

Dima Tд0kХЭто наверное в винде
в линуксе аж на расс, как 2 пальца
И в винде это есть, но шнурок к диску все равно один, я из этого исхожу, т.е. или читать или писать в один момент времени. Тормоз там.
Запись я размазываю по времени, т.е. пишется по чуть-чуть но постоянно, дальше пусть ОС оптимизирует.

Задача стояла минимум памяти, я вписался в 1 Мб стэка, поэтому магическое число 4096, а не 8192, 16384, 65536 и т.д.

Допишу, скорость IO посчитаю и тогда будет понятно надо ли что-то параллелить.

1. Не было ограничей по памяти,
было ограничение что размер файла минимум в 4 раза больше размера памяти.
То есть зависимость роста объема файла, размара требуемой
памяти и скорости сортировки должны иметь линейную зависимость.

2. Если ты используешь кеширование ФС , ты и нас и себя обманываешь .
И очень даже может быть в худшую сторону , если программа сортировки и кеш фс
не помещаются в оперативке.

3 Как показывает практика однопоточная сортировка медленнее чем
современные шпиндельные
диски на мультиблочном ввводе выводе
ни один современный процессор не в силах сортировать поток
со скоростью с которой может читать SATA3 диск ( 60 - 90 мегабайт/сек)

...

Рейтинг:

0 / 0

14.03.2017, 20:37

| Ответить | Цитировать | Написать

Тяпничная huge-сортировка

#39419316

kealon(Ruslan)

Участник

Откуда: Нижневартовск

Сообщения: 4 020

Рейтинг: 0 / 0

д0kХ,

я задачу не придумывал, такая была 20288078
учитывай что читать нужно весь объём Ln(S/MemBlockSize) раз

10 гб у меня сортировалось где то 4-5 минут, с учётом O(ln(n) * N) вроде как в твои параметры вписывается

...

Рейтинг:

0 / 0

14.03.2017, 20:48

| Ответить | Цитировать | Написать

Тяпничная huge-сортировка

#39419317

kealon(Ruslan)

Участник

Откуда: Нижневартовск

Сообщения: 4 020

Рейтинг: 0 / 0

Ln2(S/MemBlockSize) раз

...

Рейтинг:

0 / 0

14.03.2017, 20:49

| Ответить | Цитировать | Написать

Тяпничная huge-сортировка

#39419319

д0kХ

Гость

ИМХО .
Для того что бы получить скорость на современных многоядерных и многосокетных
системах нужно понимать какое соотношение полледовательного ввода вывода
и оперций seek является оптимальным для каждого диска к количеству ядер в системе.

Учитывая абстракность постановки, алгоритм должен быть
авто адаптивным по этим парамерам.

...

Рейтинг:

0 / 0

14.03.2017, 20:52

| Ответить | Цитировать | Написать

Тяпничная huge-сортировка

#39419322

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

д0kХ1. Не было ограничей по памяти,
20286712

д0kХ3 Как показывает практика однопоточная сортировка медленнее чем
современные шпиндельные
диски на мультиблочном ввводе выводе
ни один современный процессор не в силах сортировать поток
со скоростью с которой может читать SATA3 диск ( 60 - 90 мегабайт/сек)
Мне не интересна стандартная сортировка, которая O(N*log(N)) даже на сортированном файле. На сортированном хочу O(N), не надо мне *log ₂ (N), log ₂ (1Гб) = 30. Тут оно и есть, поэтому интересно.

...

Рейтинг:

0 / 0

14.03.2017, 21:08

| Ответить | Цитировать | Написать

25 сообщений из 133, страница 4 из 6

все

Форумы / Программирование [игнор отключен] [закрыт для гостей] / Тяпничная huge-сортировка

Читали тему (0):

Читали форум (0):

Пользователи онлайн (0):

start [/forum/topic.php?fid=16&msg=39418504&tid=1340453]:	0ms
get settings:	7ms
get forum list:	11ms
check forum access:	2ms
check topic access:	2ms
track hit:	53ms
get topic data:	10ms
get forum data:	2ms
get page messages:	60ms
get tp. blocked users:	1ms
others:	204ms

total:	352ms

	Необходимые cookie
	Cookie для сбора статистики
	Cookie для маркетинга и рекламы