Привет всем!
Как я уже писал, решил я приобщиться к драйверостроению. Все (ну, или почти все) мои мысли крутятся сейчас в направлении: kernel-mode. На сон грядущий после двух суток работы, пришла мне в голову интересная идея. Она заинтересовала меня настолько, что я решил поделиться ею с вами. Заключается она в том, что с помощью определенного подхода, в режиме: kernel-mode, перемещение блоков данных (особенно больших) в памяти компа, можно производить гораздо быстрее, чем это позволяют делать традиционный подход. Вообще-то, я думаю, что после того как я опишу вам этот подход, вы скажете что это банальность и что это давно известно… Но я нигде раньше не видел, чтобы кто-то предлагал этот подход для этой цели. Смысл подхода, в теории, очень прост: вместо реального перемещения данных мы просто соответствующим образом корректируем данные в каталоге и таблицах страниц… Эту операцию постоянно производит ОСь, но, IMHO, для других целей (свопинг, дефрагментация памяти, т.е. для нужд VMM). Основное и главное достоинство этого подхода, IMHO, заключается в СКОРОСТИ. На первый взгляд, при некоторых условиях, он может повысить производительность операций перемещения больших блоков данных в сотни раз, по сравнению с традиционным подходом к организации таких операций, а может быть и в тысячи, если часть перемещаемых данных, на момент операции, сброшена в своп-файл. Вот основные причины этого:
1. Операция занимает относительно очень малое кол-во времени, т.к., во-первых, требует относительно мало ‘телодвижений’. Во-вторых, все эти ‘телодвижения’ выполняются на частоте ядра процессора;
2. Позволяет забыть о том, что при оценке производительности таких операций основную роль играет не производительность процессора, а пропускная способность RAM-памяти, которая является узким местом (все необходимые данные, скорее всего, находятся в кэше);
3. В дополнение к п.2 позволяет забыть то, что во время выполнения таких операций, системе необходимо подкачивать отсутствующие в RAM страницы, из свопа.

Нужно сказать, что предлагаемый подход имеет целый ряд существенных ограничений:
1. Применим только в kernel-mode;
2. Наиболее эффективен (или даже так: эффективен только при) перемещении данных на расстояние кратное размеру страницы памяти.
3. Перемещает все содержимое страницы разом…
Я еще очень плохо ориентируюсь во внутренней работе системы (это я пытаюсь польстить себе…). Следовательно, я не в состоянии оценить перспективность предложенного подхода (бред это, или стоящая идея?). Поэтому просьба к ГУРУ, а также ко всем, кто разбирается в этом вопросе: сделайте это за меня, т.е. выскажите свое мнение по этому поводу (только, чур, больно меня, ламера, не пинать…). Если это – стоящая идея, то прошу рассказать: как это можно реально сделать.
Заранее благодарен за ваши ответы.

Можно, одну поправку: обычно при копировании блоков памяти мы хотим оставить оригинал, в вашем методе это вряд ли получится. Собственно мы просто изменим адрес нашего блока памяти. Другое дело - алгоритм WRITE_COPY, изначально присутствующая в Unix, это стоящая идея, но она уже реализованна в Win платформах.

Oleg_SK
Идея отличная! (хотя и известная в течение уже доброй пары десятков лет ;)
Увы, в существующей системе её применение практически никакого смысла не имеет: остальные модули ядра и существующие прикладные программы написаны без учёта такой возможности, и поэтому не будут пытаться пользоваться этими преимуществами... Но вот если ты будешь писать свою ОС, то... :D

Sem
Более точное название этого метода - Copy-on-Write, или "forking"

Я рад вашим ответам!

Sem
Можно, одну поправку...
Нельзя!:))) Я говорю о перемещении блоков данных, а не о их копировании. Причем, IMHO, указанный вами недостаток - очевиден...;)

Другое дело - алгоритм WRITE_COPY (Copy-on-Write)...
Спасибо за интересную инфу. Теперь, ради интереса, буду искать описание этого алгоритма...

captain cobalt
Но вот если ты будешь писать свою ОС, то... :D
Я еще слишком мелкий, для такого большого дела...

Идея отличная! (хотя и известная в течение уже доброй пары десятков лет ;)
Вот блин, я так и знал... Что ни придумаю, часто потом узнаю, что кто-то придумал это до меня. Sux.

Увы, в существующей системе её применение практически никакого смысла не имеет: остальные модули ядра и существующие прикладные программы написаны без учёта такой возможности, и поэтому не будут пытаться пользоваться этими преимуществами...
Ну и фиг с ними! Пускай пеняют на себя... У меня сейчас нет таких глобальных мыслей. Главное, чтобы мой код мог пользоваться этим методом в подходящем случае. Это может дать ему большую конкурентоспособность.

ALL
Так, раз ожидавшееся закидывание меня помидорами, похоже, не состоится, то я уточню вопрос (т.к. похоже это нужно сделать). Я прекрасно понимаю, что данный метод вряд ли подходит для стандартных функций, т.к. требует слишком специфических условий для своей реализации. Собственно, по этому я не сообщил о нем, в какой ни будь, соответствующующий этой теме, топик (хотя знаю, что тема о перемещении блоков данных уже не раз поднималась). Мне показалось, что там обсуждаются методы подходящие для стандартных функций, т.е. применимые в любых ситуациях. Теперь по поводу раздела форума... Я создал этот топик в разделе: WIN32, потому что меня интересует, возможно ли его реализовать на этой платформе или нет. Если нет, то хотелось бы узнать: что этому препятствует. Если да, то хотелось бы знать (или хотя бы, иметь представление): какие подводные камни меня подстерегают на этом пути. Собственно, хотелось бы в конце обсуждения этого вопроса (вне зависимости от его результатов) получить более четкую информацию о том, как ОСь управляет памятью (включая свопинг, управление таблицами PDE и PTE и т.п.), т.к. не имея ее, IMHO, нельзя разобраться в этом вопросе.

Sorry, спросонья спутал перемещение и копирование.

Не совсем понял, почему именно Kernel-mode и большие блоки..
Пример из жизни: сортировка не строк, а указателей на них.

Oleg_SK, один вопрос: а зачем перемещать память?

S_T_A_S_
Я рад вашему ответу!

Не совсем понял, почему именно Kernel-mode...
А как в user-mode получить непосредственный доступ к PTE, чтобы моя программа могла изменять данные в этой таблице самостоятельно?

..и большие блоки....
В PTE каждая строка описывает одну страницу памяти. Размер страницы >= 4 Kb. Таким образом, наибольшую эффективность предложенный способ имеет при перемещении блока данных, размер которого кратен размеру страницы, а начальный адрес выровнен по границе страницы, на расстояние кратное размеру страницы. Это идеальный вариант. Причем, чем больше полных страниц занимает блок данных, тем более ощутимый выигрыш по времени даст применение предложенного способа. Таким образом, как я и говорил, данный способ развивает наибольшую эффективность при перемещении больших блоков данных... Это не значит, что его нельзя применять для блоков данных, размер которых не кратен размеру страницы. Просто, в таком случае эффективность данного способа будет меньше (вплоть до полной потери смысла его применения).

Я думаю, что ответил на ваш непосредственный вопрос. Но мне думается, что вы имели ввиду не это. Похоже, вы усомнились в целесообразности применения данного метода и предложили интересный альтернативный подход. Ну что же, давайте обсудим это. Сразу возникает вопрос: уверены ли вы в том, что наши методы полностью аналогичны? Прочитав ваш пост, я стал думать. Сразу стало ясно, что у вашего способа есть один большой недостаток, который является его главным преимуществом (у любой медали есть две стороны...). Заключается он в том, что блок данных реально не перемещается в виртуальном адресном пространстве. Мне хотелось найти такой пример, который во всей красе покажет преимущества моего подхода, причем такой, с которым ваш метод не справится. В отсутствии реальной задачи это сделать трудно. Кое-что придумать удалось, хотя меня этот пример чем-то смущает (возможно, соседством с обращением к медленной дисковой памяти, хотя его можно сделать асинхронным...). Вот, собственно, сам пример:
Допустим, есть файл, состоящий из последовательности блоков данных, размеры которых кратны размеру страницы. Есть блок данных, размер которого кратен размеру страницы, а размещение выровнено на границе страницы. Необходимо добавить этот блок данных в файл к уже находящимся там блокам данных. Причем добавить не в конец, а куда-то в тело файла. Вопрос навигации в этом файле, нас, в данном примере, не волнует. Допустим, мы точно знаем позицию в файле для вставки нового блока данных. Какие наши действия при обычном подходе к этой задаче (механизм MMF тут трогать не будем):
1. В памяти выделяется входной буфер, размером с файл;
2. Загружаем во входной буфер файл;
3. В памяти выделяется выходной буфер, размером достаточным для помещения в него файла и добавляемого в него блока данных;
4. Часть исходного файла (от его начала до позиции вставки) перемещается в выходной буфер;
5. Далее, в выходной буфер перемещается вставляемый блок данных;
6. И последнее, в выходной буфер перемещается вторая часть исходного файла (от позиции вставки до его конца);
7. Сохраняем содержимое выходного буфера как результирующий файл;
8. Очищаем буферы.
Как видим, здесь часто используется операция перемещения блоков данных. Теперь рассмотрим то, какой выигрыш в данном примере даст предложенный мной способ:
1. В памяти выделяется входной буфер, размером с файл;
2. Загружаем во входной буфер файл;
3. В памяти выделяется выходной буфер, размером достаточным для помещения в него файла и добавляемого в него блока данных;
4. Часть исходного файла (от его начала до позиции вставки) проецируется в выходной буфер;
5. Далее, в выходной буфер проецируется вставляемый блок данных;
6. И последнее, в выходной буфер проецируется вторая часть исходного файла (от позиции вставки до его конца);
7. Сохраняем содержимое выходного буфера как результирующий файл;
8. Очищаем буферы.
Конкретных цифр у меня нет, но, IMHO, невооруженным взглядом видно преимущество предложенного мной способа. А вот, как применить в данном примере предложенный вами способ, я не вижу (возможно, я слеп?). Я отнюдь не настаиваю на том, что приведенный мной пример является идеальным для демонстрации преимуществ применения предложенного мной способа. Более того, вполне вероятно, что в данном примере можно применить какой-нибудь другой метод, гораздо проще моего... Но, в данном случае, нечего лучшего я придумать не смог (наверное, я слишком туп). Предложенный вами способ действительно обладает большей гибкостью, чем мой, но его возможности не перекрывают все возможности моего метода. Таким образом, они могут вполне мирно сосуществовать, помогая нам решать свои задачи...

ALL
Что-то ответов совсем мало... Наверное, это из-за того, что я недостаточно конкретизировал вопрос? OK, постараюсь еще больше конкретизировать задачу. Хотя, при задании вопроса, я хотел услышать ваши мнения по всем осям семейства Win32, но можно взять и конкретную ось. Мою. У меня стоит Windows 2000 Pro (SP4).

P.S.: У меня снова начинаются проблемы с выходом в сеть, поэтому возможны длительные задержки с моим ответом. Заранее извиняюсь.

Чего-й то я не понимаю, чего велосипед изобретать? Да еще и таким, как бы помягче, извращенным способом?
S.T.A.S. тебе предложил очень хороший пример. И самый главный, несомненный, стопроцентный плюс которого состоит как раз в том, что перемещаются не куски данных, а лишь поинтеры. А ты четко определись с условиями задачи и не высасывай примеры из пальца. Если тебе надо копировать память - то копируй себе на здоровье. Касперски почитай, DWORD'ами копируй и в KM не лезь. Если тебе нужна эффективная методика обработки больших файлов, то есть такая хитрая штука как B-Tree - в узлах дерева хранят индекс файла и поинтер в файле. Поинтер извлекается, указатель ставится, например, fpos. Более подробно см. Нимана на сайте или тут:
http://home.od.ua/~relayer/algo/data/

Наверное, это из-за того, что я недостаточно конкретизировал вопрос?

Это из-за того, что ты уж очень хитро его задал. Я так и не понял, что ты хотел спросить/сказать/поделится мнением.
Давай начнем с того, что ты определишься, что тебе, собственно, нужно и постараешься это уложить в одно предложение.

Four-F
Я рад твоему ответу!

один вопрос: а зачем перемещать память?
Прочитай мой ответ S_T_A_S_'у. Я привел там пример (правда, он надуман). Возможно, он даст ответ на твой вопрос. Возможно, позже я придумаю еще какой-нибудь пример...

В памяти выделяется входной буфер, размером с файл

Гы-гы. Положим, файл размером в гиг. Хорошо. Уже одного гига нет.

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

Ой-йо-йошеньки йо-йо. До такого даже создатели vi/vim не додумались. Эти ублюдочные редакторы просто занимают память под объем файла. А ты предлагаешь отводить В ДВА РАЗА больше памяти. Не-е-е. Я твой софт покупать не буду :)

volodya
Я рад твоему ответу!

Я так и не понял, что ты хотел спросить/сказать/поделится мнением.
Я хотел следующего:
1. Поделиться оригинальной (как я надеялся) идеей ускорения перемещения блоков данных;
2. Обсудить то, насколько она перспективна;
3. Если она бы оказалась перспективной, то узнать о способах ее реализации.
4. В ходе обсуждения п.3, я надеялся дополнительно узнать о том как ось управляет памятью на низком уровне.

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

Чего-й то я не понимаю, чего велосипед изобретать? Да еще и таким, как бы помягче, извращенным способом?
Ну, если посмотреть с этой стороны, то мне кажется что оптимизация и извращение это частенько одно и тоже;)

То есть, как я понимаю, ты считаешь что эта идея - пустышка. И что стоит забить на нее и забыть?

P.S.: Спасибо, за интересную инфу.

То есть, как я понимаю, ты считаешь что эта идея - пустышка. И что стоит забить на нее и забыть?

Я пока ее просто не понимаю.

Насколько я могу судить, тебе стоит почитать третий том Кнута - там пол-тома посвящено сортировкам. В том числе и таким, что работают с огромными файлами и очень быстро.

volodya
Ой-йо-йошеньки йо-йо. До такого даже создатели vi/vim не додумались.
Я же говорил, что это глупый пример... В реале, я бы так не поступилJ)) Просто, не смог ничего более умного придумать для того примера. И вообще, хочу обсуждать предложенный способ, а не тупость приведенного примера (я это и сам знаю).

З.Ы.: Не в тему, но все-таки: покажи оптимальный вариант, с твоей точки зрения, для подобной работы с файлом. Мне просто интересно.

Oleg_SK
Что-то я тоже ничего не пойму. Зачем память-то двигать, тем более в User Mode? Была у тебя память по адресу p1 - теперь по адресу p2. Приложению от этого ни тепло ни холодно. Или приведи пример, где это действительно надо.