Ищу алгоритм дефрагментации

Очевидно твоё использование НЕ правильное

Я тут вспомнил замечательную цитату:

Леонид Каганов, За что я ненавижу Линукс

<...> до чего мы дожили со своим техническим прогрессом! Вдумайтесь: человек ждет, пока железяка закончит свои дела и даст ему новые инструкции! Стоило ради этого спускаться с пальмы и брать в руки каменный топор? Это <...>, мир с ног на голову! А эти замечательные строчки в описаниях новых товаров: «данная видеокарта поддерживает Виндоус Висту». Не операционная система поддерживает видеокарту, нет! Видеокарта поддерживает, прогибается под соответствие системе! Железка — под программку! Моя ступня годится для новых ботинок, мой желудок поддерживает переваривание химсостава гамбургеров нового поколения, о везение! Это уже сегодня! А что же будет дальше? А дальше вслед за железкой в мясорубку отправимся мы с вами. Мы будем учиться обхаживать операционную систему, понимать операционную систему, контактировать с операционной системой. Откроются курсы по изучению психологии, привычек и мотивов поведения операционной системы, появятся тренинги «как расположить к себе операционную систему», «эффективное убеждение операционной системы», «тактика и стратегия переговоров с операционной системой»... На прилавках повылазят книжки «Чего хочет операционная система», «Как завоевать доверие операционной системы», «Искусство манипулировать операционной системой», «1001 способ произвести впечатление на операционную систему»...

Попробуй заменить «операционная система» на «файловая система».

Леонид Каганов,

он дурак. Применительно к нашей теме: посмотри, как ты организуешь своё хранилище IRL, ты всё валишь в одну кучу? Да/Нет?

Если да, то мне нечего сказать.

Если нет - то ты подо что прогибаешься? Под принципы drBatty? Не прогибайся - принцип помойного бачка - всё валим в один бак. Если что - наймём специально обученного человека, разгребать помойку.

данная видеокарта поддерживает Виндоус Висту

а ты вдумайся в слова «новая туш максфактор даёт ДЕСЯТИ кратное увеличение объёма!». Как оно тебе? И ничего, покупают... Как и карты.

А причём тут ФС?

А причём тут ФС?

Попробуй заменить «операционная система» на «файловая система».

За всё время ты не назвал ни одного алгоритма

разве алгоритм не очевиден? просто увеличиваем дырки. Файлы при этом считаются лежащими в дырках, каждый в своей(своих). Свободное пространство - некий квазифайл, который тоже лежит в своей дырке(дырках). Работа дефрагментатор заключается в том, что-бы дырки были как можно больше. Очевидно для этого их должно быть как можно меньше. Идеальная «фрагментация», когда каждый файл в своей дырке.

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

чем она лучше твоей? А твоя, кстати, какая?

Кому очевидно? Мне вот совсем не очевидно.

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

Тут я написал два абзаца гневного ответа, но вся их суть сводится к: «Нет».

обоснование будет?

Попробуй заменить «операционная система» на «файловая система».

попробовал. И что? Только не надо мне тут опять этот бред повторять, про s///g я в курсе.

да. я не в курсе, должна ли прогибаться карта под систему, но ФС должна прогибаться под данные. Это очевидно. И для разных данных должны быть разные ФС, из-за того, что совместить все требования невозможно в принципе.

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

разве алгоритм не очевиден? просто увеличиваем дырки. Файлы при этом считаются лежащими в дырках, каждый в своей(своих).

Спустись на землю :). Так можно описать алгоритм хранения данных: просто храним данные правильно. Очевидный алгоритм, хе-хе :)

чем она лучше твоей? А твоя, кстати, какая?

Смотри код. Либо жди, пока я опишу в документации. Я планирую это сделать, но не скоро.

а ты посчитай.

Я постоянно тестирую код. Для этого разворачиваю образ и запускаю дефрагментацию. У меня перед глазами числа, так что мне считать не надо. Я могу сравнивать напрямую.

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

Слушай, набросай в псевдокоде, а? Считай, что примитивы вроде «переместить конкретные блоки из позиции А в позицию Б», «перечислить все файлы» и «перечислить блоки данных и блоки метаданных определённого файла» уже есть.

обоснование будет?

Я потому и стёр, что оно излишне. Если чуть более развёрнуто: нет смысла бросать задачу на стадии 97% готовности. Особенно если эти 3% включают в себя два-три теста и написание changelog'а и займут дня два.

Спустись на землю :). Так можно описать алгоритм хранения данных: просто храним данные правильно. Очевидный алгоритм, хе-хе :)

сливать дырки можно по разному. суть от этого меняется не сильно, это всё детали реализации, которые не слишком важны.

Смотри код.

зачем мне детали реализации?

Я постоянно тестирую код. Для этого разворачиваю образ и запускаю дефрагментацию. У меня перед глазами числа, так что мне считать не надо. Я могу сравнивать напрямую.

это называется «метод тыка» - пишешь какую-то ерунду, и смотришь как оно работает. А я тебе предложил ПОСЧИТАТЬ. Это «анализ алгоритма» называется. Кстати, делается не слишком и сложно, если сильно упростить.

Слушай, набросай в псевдокоде, а? Считай, что примитивы вроде «переместить конкретные блоки из позиции А в позицию Б», «перечислить все файлы» и «перечислить блоки данных и блоки метаданных определённого файла» уже есть.

готовые алгоритмы не гуглятся?

Я потому и стёр, что оно излишне. Если чуть более развёрнуто: нет смысла бросать задачу на стадии 97% готовности. Особенно если эти 3% включают в себя два-три теста и написание changelog'а и займут дня два.

хм... 97% готовности и без changelog'а? ничего я не понимаю в современных методах разработки...

Ладно, не бросай, но хоть алгоритм в двух словах распиши. Без лишних деталей конечно.

А я тебе предложил ПОСЧИТАТЬ. Это «анализ алгоритма» называется. Кстати, делается не слишком и сложно, если сильно упростить.

Ты что, про О(f(N)) говоришь? Я тебя не понимаю.

готовые алгоритмы не гуглятся?

Я за год не нашёл ни алгоритмов, ни реализации. Тебе лень написать что ли?

хм... 97% готовности и без changelog'а? ничего я не понимаю в современных методах разработки...

git log --pretty=oneline я прямо сейчас могу сделать. Я ничего не знаю про разработку, я не писал программ до этого.

Ты что, про О(f(N)) говоришь? Я тебя не понимаю.

не только и не столько. асимптота конечно важна, но её маловато. ЕМНИП поведение сильно зависит от %% свободного места.

Я за год не нашёл ни алгоритмов, ни реализации. Тебе лень написать что ли?

я такой хренью лет 7 не занимался. да и 7 лет назад исключительно для собственного удовольствия (: Но вроде-бы я полно всякого на эту тему нашёл, в основном хлам конечно, но МНОГО. ЕМНИП самое простое начинать с того, что _можно_ сделать, и делать то, что даёт наибольший выигрыш. Как я уже сказал, в качестве метрики можно использовать общее число фрагментов. Чем оно меньше, тем лучше. Идеально N+1, где N число файлов. Конечно проще всего последовательно перебирать файлы и проверять (пытаясь собрать файл в пустом пространстве). Сразу станет заметно, что если у нас есть файл из 12345 фрагментов, и мы его соберём в свободном пространстве, то получим 12345 лишних дыр (на месте фрагментов). Потому выигрыш равен 0. Что делать, что-бы получить выигрыш? Очевидно, надо найти такой файл, что-бы некоторые из его фрагментов граничили с пустым пространством. Тогда для этих фрагментов не нужно новой дыры(число дыр не увеличивается, а число фрагментов уменьшается => +1). Надо учитывать, что файлы регулярные, и его эл-ты не допускают перестановок, за то пустой псевдофайл перестановки допускает. Потому в общем случае закрываются только пустые дырки, непустые не закрываются, за очень редким исключением. Потому вышерасмотренный случай файла из 12345 фрагментов даёт выигрыш второго порядка - хотя метрика не падает, но получается 12345 пар пусто-непусто, каждая их которых может быть слита (если конечно у нас хватит свободного места).

Сходимость такого алгоритма спорна - очевидно, при 90% св. места он сойдётся, а при 10% - нет (за обозримое время). Что будет IRL - считать тебе.

Я ничего не знаю про разработку, я не писал программ до этого.

а... тогда вопрос снимается. Просто пиши:

сегодня я сделал версию 0.1

Этого достаточно.

Сходимость такого алгоритма спорна - очевидно, при 90% св. места он сойдётся, а при 10% - нет (за обозримое время). Что будет IRL - считать тебе.

Сходу разбивается одним контрпримером. '#' — отдельные файлы, расположены каждый 20-й блок, то есть в 0-м, 20-м, 40-м и так далее. '$' — один большой файл, записан в промежутках между #, кусками по 19 блоков.

#$$$#$$$#$$$#$$$#---#---#---#---#---#---#---#---#---#---#---

Пример сходимости на менее 10% места вообще тривиален — уже дефрагментированный раздел.

Не забывай — я думал над этим. Много думал :)

Но вроде-бы я полно всякого на эту тему нашёл, в основном хлам конечно, но МНОГО.

Здесь ключевое слово — «хлам». Какой толк от сообщения, что гугл нашёл 10 миллионов результатов? Какую часть я хотя бы прочитать смогу за свою жизнь?

Допустим, размер раздела 100 тысяч блоков, размер $-файла — 1900 блоков (состоит из 100 фрагментов). Свободного места 93%, а твой алгоритм не может сдвинуть ни одного файла с места.

можно слить дырки, соединив вместе ## попарно. Я же не говорил, что начинать надо именно с $$$$$$$ файла? Нет.

А ведь под # могут скрываться метаданные, «невидимые» для этого алгоритма.

а тогда свободное место будет НЕ фрагментированое. Попробуй стереть # в последовательности #---#---#---#---#---#---#---#---#---#---#--- (ты сам сказал, что алгоритм их не видит).

Пример сходимости на менее 10% места вообще тривиален — уже дефрагментированный раздел.

это вырожденный и не имеющий значения IRL случай.

Не забывай — я думал над этим. Много думал :)

видать недостаточно. Другие думали больше...

Здесь ключевое слово — «хлам». Какой толк от сообщения, что гугл нашёл 10 миллионов результатов? Какую часть я хотя бы прочитать смогу за свою жизнь?

мда.. Дерьмовая жизнь - 7 лет назад нужное в интернетах искалось проще... Но машины времени у меня нет - извини.

ну ещё раз повторю алгоритм:

1. весь носитель естественным образом разделён на дырки, в которых лежат файлы.

2. любой файл лежит в нескольких дырках (1, 2, 3... (счётное множество)) (для особоупоротых: я знаю, что счётное множество бесконечно, для этого алгоритма это не имеет значения. Я просто не беру верхнего предела)

3. свободное пространство мы рассматриваем тоже как обычный файл, для него действует правило (2).

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

1---2---3---456---

тут цифры - это куски файла, а ---- это св. пространство. Быстрее всего убрать 123, получив

------------456123

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

1---2---3---456---

1---2------3456---

1---------23456---

---------123456---

Порядок слияния тут обеспечивается расстоянием, между элементами файла и размером результата. расстояние должно быть меньше, а размер больше. (потому мы сливаем 3 и 456, а не скажем 1 и 2)

можно слить дырки, соединив вместе ## попарно. Я же не говорил, что начинать надо именно с $$$$$$$ файла? Нет.

# — это разные файлы. Но да, если ты их можешь двигать и на каждом шаге можешь рассмотреть каждую возможность, то в этом случае действительно алгоритм действительно сработает. Если это метаданные, то этот алгоритм в тупике.

а тогда свободное место будет НЕ фрагментированое. Попробуй стереть # в последовательности #---#---#---#---#---#---#---#---#---#---#--- (ты сам сказал, что алгоритм их не видит).

Ты не можешь удалить метаданные или переписывать их. Я неоднократно упоминал, что они есть, но в твоих рассуждениях отсутствуют. Стереть имена файлов? Стой-стой, мне нужны мои имена файлов!

это вырожденный и не имеющий значения IRL случай.

Знаешь, запуск дефрагментатора на уже дефрагментированном разделе — это вполне значимый IRL случай. *в сторону, тихо* Теоретики!

видать недостаточно. Другие думали больше...

Заканчивай уже эту волынку тянуть, одно и то же талдычишь.

Дерьмовая жизнь - 7 лет назад нужное в интернетах искалось проще

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

А сейчас я расскажу поучительную историю :)

Я не математик совсем, но кодить вроде могу. И вот понадобилось нам как-то решать одно уравнение много-много раз. Посмотрели на задачу, придумали сетку, вывели сеточные уравнения, свели к линейным. Надо решать СЛАУ. А надо сказать, матрица плохо обусловленная (не знаю точных терминов) и решается СЛАУ плохо.

Мы студенты, мы ничего не знаем, зато есть умный препод, который всё знает хорошо. Он нам выкатывает алгоритм, мы его реализуем, а он не работает. Известно кто виноват — студенты, они же глупые и неопытные, а препод уверен в своём методе. Мучались месяц, осмелились попросить proof-of-concept. Он нам его выкатил.

Свой метод он проверял на матрицах 17x17, тогда как нам нужно было считать на матрицах 100000x100000. Теоретик. Он забыл, что на таких мелких матрицах работает любой® метод, да хоть простые итерации.

Понимаешь теперь, почему я так отношусь к чисто-теоретическим суждениям? Если человек не набил шишки на реализации своих чудо-алгоритмов, веры ему нет. Поверю только после доказательства. (Хочу отметить: я не требую.)

А теперь ближе к задаче. Ты выдумываешь алгоритмы исходя из своих предположений о стоимости передвижения блока. Передвинуть блок? Да там всего-лишь записать его содержимое в другое место! Это так только с точки зрения теории. На практике тебе нужно ещё поправить метаданные, обновив в них положение данных. Скажешь просто? Но ведь метаданные надо ещё найти.

Предложенные алгоритмы ограничиваются тем, что может обозреть человек. Машине же приходится иметь дело с намного большими размерами. Алгоритм, который ты привёл, полагается на исполнителя, его возможность обозреть всю карту раздела целиком. А в реализации ты будешь практически слеп. Машине нужно всё разложить по полочкам, все эвристики. Эвристики алгоритма это не детали реализации, это и есть сам алгоритм. Без них остаются только очевидные высказывания. «При дефрагментации нужно уменьшить число фрагментов». Да вы что?! Никогда бы не догадался.

Пример: перемещение K блоков занимает время C1 + C2*K*log(K), если ты перемещаешь их скопом. И K*(C1+C2), если по одному. C1 и С2 — это «почти константы», они зависят от паттерна доступа к диску. Если блоки рядом, то C2 ≈ 0.04 мс, если блоки случайные (как у тебя), C2 ≈ 12-15мс. В первый раз С1 ≈ 2 минуты, в последующие С1 ≈ 1-2 секунды. Это если у тебя есть достаточно ОЗУ, чтобы держать всё дерево в ней целиком. (Это у меня так было на тестовом разделе, 120 гигов, 96 заняты распакованным main от debian testing)

# — это разные файлы. Но да, если ты их можешь двигать и на каждом шаге можешь рассмотреть каждую возможность, то в этом случае действительно алгоритм действительно сработает.

пофиг, что разные. См. выше - при слиянии даже разных файлов фрагментация св. пространства уменьшается. Это тоже хорошо. Причём тут шаги? Понятно, что $$$$$$ слить не получится, и что теперь? Топиться или перейти к рассмотрению других возможностей?

Если это метаданные, то этот алгоритм в тупике.

Ты не можешь удалить метаданные или переписывать их. Я неоднократно упоминал, что они есть, но в твоих рассуждениях отсутствуют. Стереть имена файлов? Стой-стой, мне нужны мои имена файлов!

не переживай. У тебя имеется связанное множество - поверхность носителя. Но, из-за метаданных множество несвязанное. Тебе кажется, что это что-то меняет? Нет. Убери метаданные, и множество опять обретёт связанность. Возьми к примеру множество составных чисел, которые можно разложить на 2 и более делителя. Это множество рваное и несвязанное. Ну и что? Выкидывай нафиг простые числа, и перенумеровывай своё множество по новой - получишь непрерывное счётное связанное множество. 4,6,8,9,10,12,14,15,16,18... Алгоритм от этих манипуляций ну никак не меняется.

Знаешь, запуск дефрагментатора на уже дефрагментированном разделе — это вполне значимый IRL случай. *в сторону, тихо* Теоретики!

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

Если свободный блок единственный, то комбинировать его можно. И даже всегда очевидно как именно. Однако гонять даже твои 3Гб через блок в 4К - это будет очень долго... Это можно кстати и посчитать, дабы отписать юзеру: «дефрагментация закончится через Over9000 часов», используя тот факт, что мы можем рассчитать минимальное время сходимости.

Свой метод он проверял на матрицах 17x17, тогда как нам нужно было считать на матрицах 100000x100000. Теоретик. Он забыл, что на таких мелких матрицах работает любой® метод, да хоть простые итерации.

бред. Если мы доказали, что асимптота равна O(f(N)), то мы в праве считать на мелких матрицах 17х17, аппроксимируя их на большие. К примеру если f(N) === N*N, и время выполнения 12345 тактов на матрице 17х17, то на матрице 100000 время выполнения будет заведомо меньше (100000/17)^2 *12345 тактов. (427 162 629 757 тактов)

бред. Если мы доказали <...> то мы в праве считать на мелких матрицах

А он не доказал. Ты тоже. :)

то на матрице 100000 время выполнения будет заведомо меньше

я всё никак не могу взять в толк, являешься ты программистом, математиком или кем-то другим (по образованию).

В написанном тобой есть небольшие неточности, которые математик вряд ли бы допустил. Предположение, что время работы алгоритма на матрице линейно зависит от числа элементов в ней, неверно. Число элементов в матрице N^2, а LU-разложение (в простейшей форме) занимает N^3. И ещё момент. Такие большие матрицы всегда разреженные, а там оценка скорости может быть N, особенно если диагоналей штук 5-9.

А программист вспомнил бы про кэш. 17-на-17 легко влазит в кэш, а 100000-на-100000 уже гарантированно нет. Я могу сделать скидку на программиста, который работал в 80-х, когда доступ к памяти был «бесплатным», но 7 лет назад проблемы оптимизации доступа к памяти уже давно стояли в полный рост.

Ну как, у меня получается быть гадалкой? :)

А теперь ближе к задаче. Ты выдумываешь алгоритмы исходя из своих предположений о стоимости передвижения блока. Передвинуть блок? Да там всего-лишь записать его содержимое в другое место! Это так только с точки зрения теории. На практике тебе нужно ещё поправить метаданные, обновив в них положение данных. Скажешь просто? Но ведь метаданные надо ещё найти.

это никак не сказывается на сходимости и вычислительной сложности алгоритма.

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

причём тут я? твой алгоритм плохо видит? Это твоя проблема, что на твоём разделе сумеречные зоны. И причём тут размер? Я брал счётное множество фрагментов, т.е. бесконечность.

«При дефрагментации нужно уменьшить число фрагментов». Да вы что?! Никогда бы не догадался.

КАК уменьшать ты тоже догадался?

Пример: перемещение K блоков занимает время

это усложнение также не влияет на сходимость. Называется «преждевременная оптимизация». Для начала считай, что время перемещение блока равно константе - такой алгоритм пригодится для RAM & SSD. Потом можно добавить необходимых эвристик, это уже частный случай.

А он не доказал. Ты тоже. :)

если он не доказал - это его проблема. Что до меня, то мне просто нет смысла заниматься бессмысленным трудом. Я уже говорил о том, что восстановление из бекапа очевидно быстрее и проще. Бекап есть. В чём проблема? Помогать админам, которые ещё не делают бекапов считаю глупостью.

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

я в курсе. Это не неточность, это просто пример. Не забывай о том, что я вообще не в курсе, какие вы там матрицы считали. И что вы с ними делали. Например обнуление матрицы NxN прямо пропорционально квадрату N. Сложение матриц - тоже.

Такие большие матрицы всегда разреженные

это у тебя они всегда разряжённые.

а там оценка скорости может быть N

что-то я тебя не пойму, N^3 бывает, N^1 бывает, а вот N^2 не бывает? Почему?

А программист вспомнил бы про кэш. 17-на-17 легко влазит в кэш, а 100000-на-100000 уже гарантированно нет.

я про него и не забывал. Вот только кеш никак не влияет на асимптоту. К тому же я действительно программист, а не теоретик - числа у тебя были целые? Уверен - не целые, а всякие double, а их уже много лет считают на сопроцессоре, при этом время выборки из памяти не сильно влияет на скорость (строки матрицы читаются одновременно с вычислением). Вообще говоря, IRL кеш на матричных операциях работает очень плохо, т.к. совсем не заточен под выборку непоследовательно. Даже на твоей матрице в 2312 байт кеш будет только мешаться. Да, в сопроцессоре конечно тоже есть свой кеш, но не думаю, что тебя устроит 8и регистровый стек.

Я могу сделать скидку на программиста, который работал в 80-х, когда доступ к памяти был «бесплатным», но 7 лет назад проблемы оптимизации доступа к памяти уже давно стояли в полный рост.

кеш тебе поможет при _последовательном_ доступе. В матрицах половина операций со столбцами, а читать через 17*8=136 байт довольно уныло, и кеш от этого только забивается мусором... Можешь сам проверить...

ЗЫЖ и да, опять преждевременная оптимизация во все поля.

причём тут я? твой алгоритм плохо видит? Это твоя проблема, что на твоём разделе сумеречные зоны. И причём тут размер? Я брал счётное множество фрагментов, т.е. бесконечность.

Да, проблема моя. А размер тут притом, что он влияет на вычислительную сложность. Сколько времени займёт поиск подходящего места для блока? N? А сколько блоков? N? Когда я перемножаю N и N, мне становится грустно. На маленьких размерах не видно квадратичной сложности.

это усложнение также не влияет на сходимость. Называется «преждевременная оптимизация». Для начала считай, что время перемещение блока равно константе - такой алгоритм пригодится для RAM & SSD.

Не влияет на сходимость, но влияет на скорость, причём значительно. Это не преждевременная оптимизация. Это осознанный выбор между NlogN и N^2. Может быть ты не знал, но на крошечных массивах сортировка пузырьком быстрее, чем Quicksort. И я не зря привёл по два значения «констант». Второе — это и есть случай, когда всё уже в RAM.

Уверен - не целые, а всякие double, а их уже много лет считают на сопроцессоре,

http://en.wikipedia.org/wiki/SSE2

кеш тебе поможет при _последовательном_ доступе. В матрицах половина операций со столбцами, а читать через 17*8=136 байт довольно уныло, и кеш от этого только забивается мусором... Можешь сам проверить...

http://math-atlas.sourceforge.net/faq.html#what

Да, проблема моя. А размер тут притом, что он влияет на вычислительную сложность. Сколько времени займёт поиск подходящего места для блока? N? А сколько блоков? N? Когда я перемножаю N и N, мне становится грустно. На маленьких размерах не видно квадратичной сложности.

мне всё прекрасно видно. ты придумал какой-то новый алгоритм? кстати, почему время поиска у тебя пропорционально N? Если у тебя N, то что ты предлагаешь? Грустить?

Не влияет на сходимость, но влияет на скорость, причём значительно. Это не преждевременная оптимизация. Это осознанный выбор между NlogN и N^2. Может быть ты не знал, но на крошечных массивах сортировка пузырьком быстрее, чем Quicksort

нет, не знал. Ты не путаешь сортировку пузырьком и сортировку простыми вставками? И не нужно прыгать - то у тебя «необозримо много, грустно N*N», а то ты вдруг сбиваешься на «небольшие массивы», определись уж...

Да и вообще определись наконец - У ТЕБЯ какой алгоритм? Ты его можешь только в виде исходника выразить, или на русском тоже сумеешь?

http://en.wikipedia.org/wiki/SSE2

и что? Это как-то поможет разместить 17*17 чисел в 8и регистрах, да ещё и вместе с промежуточными результатами?

http://math-atlas.sourceforge.net/faq.html#what

эту ссылку покажи своему преподавателю, а не мне. Мне-то смысл доказывать? Это не я концепт разряжённой матрицы 17*17 сделал. Я даже не знаю, что вы там считали, да и знать не желаю. Я могу одно сказать - матрица 17*17 в кеш сейчас не влезает, а тем более не влезала раньше. И ещё могу сказать, что размер 17 вполне достаточен для выводов, если алгоритм тот же самый (я правда никогда не встречал разряжённых матриц размерности 17, и не представляю, какой в них смысл)

кстати, почему время поиска у тебя пропорционально N?

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

нет, не знал. Ты не путаешь сортировку пузырьком и сортировку простыми вставками?

Без разницы. Главное, что он O(N^2)

И не нужно прыгать - то у тебя «необозримо много, грустно N*N», а то ты вдруг сбиваешься на «небольшие массивы», определись уж...

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

Да и вообще определись наконец - У ТЕБЯ какой алгоритм? Ты его можешь только в виде исходника выразить, или на русском тоже сумеешь?

Раздел делится на группы аллокации (AG) — блоки по 128 МиБ. Для каждой AG поддерживаем список свободных экстентов. Дефрагментацию выполняем проходом по всем файлам. Каждый файл делим на куски по 8 МиБ. Если кусок фрагментирован, находим для него место в следующем AG. Если не нашли, ищем во всех остальных AG. Если не нашли, пытаемся раскидать наиболее свободный AG, если и после этого не получилось, облом, выходим. Переходим к следующему куску. Если были обломы, проход повторяем.

Место в AG ищем так: наименьший экстент, в который влезает кусок запрошенного размера.

и что?

Это к тому что сопроцессор x87 считается устаревшим и его использование не поощряется. Он есть для совместимости, но жрёт драгоценные такты. SSE2 гораздо быстрее и не ограничен стековой моделью.

Я могу одно сказать - матрица 17*17 в кеш сейчас не влезает, а тем более не влезала раньше.

Ты что, издеваешься? У меня L2 кэш в 2М, а ты говоришь, что 2 килобайта в кэш не влезут?

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

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

Без разницы. Главное, что он O(N^2)

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

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

ну это зависит исключительно от того, какое у тебя N - можно доказать, что есть вполне конкретное N, при котором влияет _только_ асимптота, если конечно константы и f(N) известны. Ну к примеру простые вставки начинают сосать у qsort уже где-то с 10..15и, и чем дальше, тем только всё хуже и печальнее. Что касается пузырька, то оно начинает сосать ещё с 2х, потому пузырёк вообще нет смысла юзать, для _любых_ N. Твоё утверждение «О не самоцель» нуждается в доказательстве - При КАКОМ N это не самоцель? Сдаётся мне, что это N будет очень небольшим...

Раздел делится на группы аллокации (AG) — блоки по 128 МиБ. Для каждой AG поддерживаем список свободных экстентов. Дефрагментацию выполняем проходом по всем файлам. Каждый файл делим на куски по 8 МиБ. Если кусок фрагментирован, находим для него место в следующем AG. Если не нашли, ищем во всех остальных AG. Если не нашли, пытаемся раскидать наиболее свободный AG, если и после этого не получилось, облом, выходим. Переходим к следующему куску. Если были обломы, проход повторяем.

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

Это к тому что сопроцессор x87 считается устаревшим и его использование не поощряется. Он есть для совместимости, но жрёт драгоценные такты. SSE2 гораздо быстрее и не ограничен стековой моделью.

SSE2 есть только в iP4, причём его быстродействие в атоме остаётся под большим вопросом... Ну и x87 ещё и намного точнее, а стек не является багом, но фичей. SSE2 хоть и позволяет произвольную адресацию восьми регистров, но в одном регистре должно быть два числа, что тоже является важным ограничением.

Ты что, издеваешься? У меня L2 кэш в 2М, а ты говоришь, что 2 килобайта в кэш не влезут?

Я не про L2. И да, хватит уже ерунду пороть - твой препод прототип на ассемблере под SSE2 писал что-ли?

И ты не понял самого главного, о чём я говорил в разрезе матриц - что мелкие матрицы, что большие разряжённые, имеют общую особенность - там вычислений довольно много, по сравнению с чтением/записью. Потому, то, что они в твой кеш влазят, погоды не делает. Если тебе надо 3К из памяти прочитать (не из кэша!), то читать тебе всё равно придётся, потому кеш тут тебе совсем не поможет, если матрица маленькая, а если она большая, то тоже не поможет, ибо чтение/запись отнюдь не последовательное.

конечно! перебор _всех_ блоков необходим только в одном случае <...>

Ты сейчас на таких высотах, что разговор бессмыслен. Где оценки вычислительной сложности? Тем более, что доказывал (методом «это очевидно») ты сходимость только для случая, когда ищется оптимальное место. А это значит, что раз ты изменил свой алгоритм, значит сходимость нужно доказывать заново.

а почему такая жёсткая привязка к мегабайтам?

Потому что мне надо, чтобы работало. Компьютер плохо переваривает абстрактные размышления. Ему программу подавай. А ещё диски не любят, когда с них читают маленькими блоками.

в принципе, у тебя некий частный случай моего общего алгоритма, не?

Не... это у тебя упрощённая и недоделанная версия моего :-)

Где оценки вычислительной сложности?

нету. мне-то оно зачем?

Тем более, что доказывал (методом «это очевидно») ты сходимость только для случая, когда ищется оптимальное место.

почему сразу «оптимальное»?

Потому что мне надо, чтобы работало. Компьютер плохо переваривает абстрактные размышления. Ему программу подавай. А ещё диски не любят, когда с них читают маленькими блоками.

что значит «абстрактные» и «маленькие»? Привяжи к размеру блока например... Или к размеру раздела. Скажем AG = размер_раздела/256.

Не... это у тебя упрощённая и недоделанная версия моего

ну это как посмотреть. у меня проще для анализа. но делать этот анализ да, лень...

SSE2 есть только в iP4, причём его быстродействие в атоме остаётся под большим вопросом...

Вылезай из криокамеры, уже 2012-й год кончается. Pentium 4 появились 11 лет назад. А на атоме расчёты делают только гики.

а стек не является багом, но фичей

Про блокировки я не буду рассказывать, хорошо?

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

int main(void)
{
  double q1 = 0.0, q2 = 1.0, q3;
  q3 = q1 + q2;
}

0000000000000000 <main>:
   0:        55                           push   %rbp
   1:        48 89 e5                     mov    %rsp,%rbp
   4:        b8 00 00 00 00               mov    $0x0,%eax
   9:        48 89 45 f8                  mov    %rax,-0x8(%rbp)
   d:        48 b8 00 00 00 00 00         movabs $0x3ff0000000000000,%rax
  14:        00 f0 3f 
  17:        48 89 45 f0                  mov    %rax,-0x10(%rbp)
  1b:        f2 0f 10 45 f8               movsd  -0x8(%rbp),%xmm0
  20:        f2 0f 58 45 f0               addsd  -0x10(%rbp),%xmm0
  25:        f2 0f 11 45 e8               movsd  %xmm0,-0x18(%rbp)
  2a:        5d                           pop    %rbp
  2b:        c3                           retq 

Я не про L2. И да, хватит уже ерунду пороть - твой препод прототип на ассемблере под SSE2 писал что-ли?

Посмотри на код выше. Этот код был скомпилен вот так: gcc -c q.c . Уже давно для вычислений с плавающей точкой используется SSE2 по умолчанию.

Потому, то, что они в твой кеш влазят, погоды не делает.

Я уже приводил пример libatlas, но ты от него отмахнулся. Зря. at в названии означает, что производится настройка под размер кэша. Операции с матрицами производятся блочно, таким образом, чтобы блоки влезали в кэш. Не пытайся быть умнее реальности. libatlas — работает.

что значит «абстрактные» и «маленькие»?

Маленькие это меньше чем <скорость чтения> * <время позиционирования головки>.

Привяжи к размеру блока например... Или к размеру раздела. Скажем AG = размер_раздела/256.

Зачем?

у меня проще для анализа. но делать этот анализ да, лень...

Это потому что для анализа потребуется заполнить логические дыры. Обрастёт деталями реализации.

а стек не является багом, но фичей

Про блокировки я не буду рассказывать, хорошо?

что не так с блокировками? почему стек из 8и регистров блокируется, а 8 регистров - не блокируется?

q3 = q1 + q2;

ну и что? для того, что-бы код SSE2 был более эффективнее, чем x87, нужно в одном регистре хранить два числа. А так скорость такая же, а точность ниже плинтуса.

Посмотри на код выше. Этот код был скомпилен вот так: gcc -c q.c . Уже давно для вычислений с плавающей точкой используется SSE2 по умолчанию.

как оно не странно, это совсем не всегда хорошо, вот тесты: [gentoo][gcc]-mfpmath

Зачем?

что-бы хорошо работало на любых разделах. Сам-же делаешь концепт «матрицы 17*17».

Я уже приводил пример libatlas, но ты от него отмахнулся. Зря. at в названии означает, что производится настройка под размер кэша. Операции с матрицами производятся блочно, таким образом, чтобы блоки влезали в кэш. Не пытайся быть умнее реальности. libatlas — работает.

ну если подстраивать...

что-бы хорошо работало на любых разделах. Сам-же делаешь концепт «матрицы 17*17».

Вот как раз, чтобы работало на любых разделах и делаю так, как сказал. Подход «N/256» даёт квадратичную сложность.

ну если подстраивать...

Добро пожаловать на землю.

Вот как раз, чтобы работало на любых разделах и делаю так, как сказал. Подход «N/256» даёт квадратичную сложность.

причём тут сложность-то?

Добро пожаловать на землю.

концепт не нужно подстраивать под размер кеша, лишь-бы работал.

как оно не странно, это совсем не всегда хорошо, вот тесты: [gentoo][gcc]-mfpmath

Что-то они какие-то странные. Я попробовал сам.

rinat@f-laptop:/tmp/4$ gcc -O3 -m32 -mfpmath=387 -lrt q.c && ./a.out 
benchmarking
elapsed = 16.01516 sec
rinat@f-laptop:/tmp/4$ gcc -O3 -m32 -msse2 -mfpmath=sse -lrt q.c && ./a.out 
benchmarking
elapsed = 8.26469 sec

Умножал две матрицы 1000 на 1000.

концепт не нужно подстраивать под размер кеша, лишь-бы работал.

Концепт — память можно свопать на диск. В этом случае, RAM — это кэш. Запусти задачу, требующую больше RAM, чем есть физически и объясни пользователям, что концепт работает, а они получат результаты. Ну, когда-нибудь.

причём тут сложность-то?

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

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

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

P.S.

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

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

однозначно. насколько я помню, там нет ничего сложного, но вдаваться мне в это совсем не хочется.