Oberon space
General Category => Общий раздел => Тема начата: ilovb от Март 06, 2012, 02:30:05 pm
-
Есть у меня крамольная мысль сваять текстовый редактор. Изначально мысль родилась на оберкоре (http://forum.oberoncore.ru/viewtopic.php?f=47&t=3360&start=20)в процессе поиска причины диких тормозов ЧК на больших неприлично раскрашенных документах. Тогда выяснилось, что причиной является архитектурная особенность текстовой подсистемы. Оказалось что система перед отображением текста сканирует документ снизу вверх в поисках линейки. Решение мягко сказать деревянное. Если поиск линеек закоментить, то тормоза практически пропадают. Но это еще не все... Пока я ковырял текстовую подсистему, то обратил внимание, что система далеко не так проста как может сначала показаться. В общем наворочено там не мало... Довольно сложно и не понятно зачем. На эту сложность и Сергей Губанов обращал внимание. Прикрутить свистоперделки к ней как в современных редакторах кода если не невозможно, то довольно сложно. Саму текстовую подсистему с наскока вкурить вообще нереально имхо. (это я над блэкбоксовой обозримостью стебаюсь ;)) Т.е. приходится долго и упорно читать код самой подсистемы, чтобы быть уверенным что ты ее правильно используешь. Хорошего понимания как она работает похоже нет ни у кого (возможно я ошибаюсь конечно)
Ладно... о чем это я?!
Ах да.
Изначально я хотел сваять простенькую, но расширяемую текстовую модель типа нотепад (а остальное (форматирование там всякое) прикрутить в расширении этой модели). Оберкоровцы в последнем сраче мне это желание поубавили.
В общем на данный момент у меня осталось желание этим заняться, но не ради переделки текстовой подсистемы ЧК, а для общего развития так сказать. :) Если в итоге кому-то будет польза, то гуд, если нет то нет...
Опыта конечно нет в таких задачах, и супермЭном-вундеркиндом-одиночкой я себя не считаю. Некоторые мысли есть, но пока в процессе переваривания. Пытался в инете найти информацию на эту тему, но безрезультатно.
В общем прошу помочь соображениями и информацией по этой теме. Ну и стоит ли вообще велосипед городить? Ценный ли это опыт будет?
Если кто уже занимался подобной задачей, то поделитесь опытом плиз. ::)
ps Во накатал то... уф...
-
Опыт он конечно опыт и ценный. На счет архитектуры расширяемого текстового редактора пока не подскажу (просто я не слишком понимаю что в нем должно быть - это составной документ, или как?). Но подскажу в сторону алгоритмов и структур данных для редактирования больших текстов: rope (http://en.wikipedia.org/wiki/Rope_(computer_science)).
-
По идее неплохо бы было иметь хотя бы специализированную компоненту для подсветки текста (раскраска не нужна и возможностью подключения доп . приблуд вроде intellisensa , codecompletion) кода, частично идея была реализована С. Губановым - но до презентабельного уровня не доведено ... А вы рассматривали возможность внедрения ГОТОВОГО компонента - вроде коровцы били себя в грудь что это реально :( веры конечно никакой... пусть даже ПЛАТНОГО -что там 100$
это ГРОШИ по сравнением с возможностью получить КАЧЕСТВЕННЫЙ результат в ПРИЕМЛЕМОЕ время....
-
пример http://www.econtrol.ru/syntedit.html (http://www.econtrol.ru/syntedit.html)
-
Но подскажу в сторону алгоритмов и структур данных для редактирования больших текстов: rope (http://en.wikipedia.org/wiki/Rope_(computer_science)).
Не ожидал, что вот так прям сразу мне ссылку дадут. Спасибо!
Вот я гуглер бестолковый ;D
-
...просто я не слишком понимаю что в нем должно быть - это составной документ, или как?
Просто поддержка форматированных документов. Атрибуты текста, форматирование абзацев, вставка картинок и т.д. и т.п. Если текстовый редактор в ЧК, то конечно и вьюхи нужно поддерживать. Но это все в расширении модели. А базовая модель должна быть проста "как пробка". Т.е. должна быть возможность работать с простой моделью, на базе которой можно построить приличный редактор кода.
-
Не ожидал, что вот так прям сразу мне ссылку дадут. Спасибо!
Вот я гуглер бестолковый ;D
Собственно, в ББ и в Обероне та же структура для текстов.
-
подскажу в сторону алгоритмов и структур данных для редактирования больших текстов: rope (http://en.wikipedia.org/wiki/Rope_(computer_science)).
Мозги свернёшь пока поймёшь :)
Я думаю такие сложные структуры были изобретены во времена когда оперативной памяти в компьютере было мало. Сейчас это не очень актуально, поэтому можно использовать более простую структуру данных -- двухсвязный список. Текст -- это двухсвязный список символов. Каждый символ имеет указатель на предыдущий и следующий символ текста, а так же указатель на атрибуты, ну и свой код.
Чтобы не замучить менеджер памяти огромадным количеством мелких объектов (http://oberspace.dyndns.org/index.php/topic,173.0.html), надо для них использовать свой менеджер памяти, например, разместить их на массивах структур -- будет летать со скоростью света.
Имея ввиду организацию двухсвязного списка на массиве структур получаем что-то вроде такого:
public struct Symbol
{
public uint value; // код этого символа
public uint attributes; // индекс в массиве атрибутов -- атрибуты этого символа
public uint prev; // индекс в массиве символов -- предыдущий символ текста
public uint next; // индекс в массиве символов -- следующий символ текста
}
public struct Attributes
{
public uint font; // индекс в массиве шрифтов
public uint size; // размер шрифта
public uint color; // цвет символа
public uint flags; // всякие флаги: жирный, наклонный, подчёркнутый, зачёркнутый...
}
В массиве атрибутов элементы лучше сделать уникальными, тогда можно будет легко вычислять равенство и неравенство аттрибутов имея лишь индексы массива: если индексы не равны, то и атрибуты не равны.
Расход памяти на символ - 16 байтов, то есть на документ из миллиона символов уйдёт 16 мегабайтов. Лет 20 назад за такое злодеяние программиста бы расстреляли, а сейчас нормально. Подумаешь каких-то там 16 мегабайт...
Ну, в общем, я думаю как-то так...
-
Это было изобретено не столько для экономии памяти, сколько ради сложности операций. Там все сложности (кроме build) O(log(n)), в списке же тот же search будет O(n).
-
Собственно, в ББ и в Обероне та же структура для текстов.
Это точно? Я что-то не помню там такого :(
Эта структура же в 1995 вроде опубликована была (по данным в Wiki)
Когда я копался в текстовой подсистеме ЧК, мне показалось что она использует линейный связанный список. Я не исключаю конечно что плохо смотрел :)
Забавно. Это получается Вирт эту структуру раньше изобрел?!
-
Это было изобретено не столько для экономии памяти, сколько ради сложности операций. Там все сложности (кроме build) O(log(n)), в списке же тот же search будет O(n).
А что там имеется в виду под словом search?
Для эффективного поиска подстрок нужно создать дополнительную структуру ("проиндексировать текст"). Эта дополнительная структура будет лежать рядышком и не отменять основную (не вместо, а вместе).
-
Кстати, задача огромной важности которую ещё надо решить это организация механизма отмены совершённых правок (undo/redo).
-
Было бы неплохо делать текстовый редактор вместе с IDE
-
Вот еще пара ссылок:
http://www.ibm.com/developerworks/ru/library/j-ropes/ (http://www.ibm.com/developerworks/ru/library/j-ropes/)
http://fprog.ru/2010/issue6/eugene-kirpichov-incremental-regular-expressions/ (http://fprog.ru/2010/issue6/eugene-kirpichov-incremental-regular-expressions/)
-
Это было изобретено не столько для экономии памяти, сколько ради сложности операций. Там все сложности (кроме build) O(log(n)), в списке же тот же search будет O(n).
А что там имеется в виду под словом search?
Definition: Search(i): return the character at position i
То же мне сёрч. Для текстового редактора извлечение буквы находящейся в позиции i=1'234'567 не актуальна. Куда актуальнее чтобы вставка/удаление подстрок выполнялась за О(1). Для текстов из миллионов букв, кстати, разница между O(1) и O(log(N)) может стать заметной, так что двухсвязный список символов рулит.
-
Если не ставить перед моделью задач помимо обеспечения эффективной работы ядра текстового редактора, то да. :) Эффективное произвольное позиционирование и/или задача извлечения символа по индексу нужны только при программной работе с текстом. А манипуляции текстом в редакторе в основном как "на рельсах" происходят. Двусвязного списка достаточно.
Если говорить про произвольное позиционирование по номеру строки в редакторе (Ctrl+"G"), то тут не грех и линейным поиском...
-
Еще ссылочка:
http://rsdn.ru/article/cpp/segmented_list.xml (http://rsdn.ru/article/cpp/segmented_list.xml)
-
Всё что я раньше сказал про двухсвязный список отправляется в сад ибо уже не актуально... :)
Сейчас измерил на современном компьютере время вставки элемента в массив -- оно ничтожно. Поэтому для представления текста на современном компьютере уже не нужны никакие там сложные структуры, а достаточно взять просто массив символов. Вставляешь символ -- тупо сдвигаешь все последующие символы на одну позицию и не паришься на счёт того, что это якобы медленно. Уже не медленно!!!
И так. Номер буквы - 4 байта, номер атрибутов - 4 байта, итого 8 байтов на символ. Измеряем сколько времени займёт вставка символа в позицию 0 если длина текста 1'000'000 восьмибайтовых символов.
public void Insert (int position, long value)
{
this.length++;
// this.CheckCapacity();
for (int n = position; n < this.length; n++)
{
long t = this.array[n];
this.array[n] = value;
value = t;
}
}
Получаем всего лишь 962 микросекунды на Core i7 2600K с памятью DD3 1600 MHz.
Не забываем, что в 2014 появится DDR4 которая раза в два-три быстрее чем DDR3.
-
Получаем всего лишь 962 микросекунды на Core i7 2600K с памятью DD3 1600 MHz.
Не забываем, что в 2014 появится DDR4 которая раза в два-три быстрее чем DDR3.
Интересней были бы тесты на, скажем, intel atom. Ибо в качестве печатной машинки (текстового редактора) обычно таки именно подобные дивайсы используют. Ну и на arm'e.
-
Сейчас измерил на современном компьютере время вставки элемента в массив -- оно ничтожно. Поэтому для представления текста на современном компьютере уже не нужны никакие там сложные структуры, а достаточно взять просто массив символов. Вставляешь символ -- тупо сдвигаешь все последующие символы на одну позицию и не паришься на счёт того, что это якобы медленно. Уже не медленно!!!
Если уж пример на C#, то там для этого есть более эффективный метод - Array.Copy(...)
-
С System.Array.Copy получилось 535 микросекунд.
-
У меня нет intel atom, зато дома есть Pentium 4. Потом измерю на нём. Но даже если будет в десять раз медленнее, так ведь текст в 1'000'000 символов тоже ого-го. Обычно тексты сильно короче.
-
У меня нет intel atom, зато дома есть Pentium 4. Потом измерю на нём. Но даже если будет в десять раз медленнее, так ведь текст в 1'000'000 символов тоже ого-го. Обычно тексты сильно короче.
Это ж всего лишь мегабайтный текст. А логи например бывают и по 100 мегабайт. Или скажем какой-нибудь дамп базы. Понятно что по уму с ними надо работать не через текстовый редактор, но иногда под рукой просто больше ничего нет.
-
Бывают и многогигабайтные текстовые файлы до 200млн строк (сам с такими работаю).
-
Если файл на столько большой, то и нечего загружать его целиком в редактор. Используем скользящее окно в миллион букв.
-
Да... решение в лоб :D
Я ради опыта конечно веревки скорее всего буду использовать. Однако простой двусвязный список тоже привлекателен. Я тут на днях обнаружил что в книжке "Прожект Оберон" есть описание архитектуры тамошней текстовой подсистемы. В основе то же что в ЧК. Но разработчики ЧК столько там насвистоперделили, что разглядеть виртовскую элегантность уже трудно. :)
Надо оригинальный Оберон поглядеть...
-
Интересней были бы тесты на, скажем, intel atom. Ибо в качестве печатной машинки (текстового редактора) обычно таки именно подобные дивайсы используют. Ну и на arm'e.
Если Fusion E450 катит, то кидайте свой тест сюда. Замеряем время. Только не забудьте сказать версию нета. Не уверен, что у меня оно вообще есть, а всё подряд ставить на комп тоже не особо хочется.
-
Это ж всего лишь мегабайтный текст. А логи например бывают и по 100 мегабайт. Или скажем какой-нибудь дамп базы. Понятно что по уму с ними надо работать не через текстовый редактор, но иногда под рукой просто больше ничего нет.
Редактировать логи - это сильно : ). Разговор с заказчиком: "Я тут посмотрел свои логи {но мы-то знаем...} - никаких проблем. Или проблема не на нашей стороне".
Сто мегабайт - это сто массивов по 1 мегу.
А несколько гигов в ОЗУ загрузить... Я таки вас умоляю, не говорите мне, что собираетесь прочесть каждую строчку лога. А грепами лог вполне можно уменьшить до приемлемого размера.
-
Всё что я раньше сказал про двухсвязный список отправляется в сад ибо уже не актуально... :)
Стопудово :) Я вот когда в свою контору пришел был сначала удивлен использованию векторов там, где казалось бы "по всем правилам" должен был быть список (вставка в середину, удаление из середины). Однако на практике оно тупо быстрее :)
-
Если Fusion E450 катит, то кидайте свой тест сюда. Замеряем время. Только не забудьте сказать версию нета.
namespace TestCopy
{
public sealed class ArrayString
{
private long[] array;
private int length;
public ArrayString (int length)
{
this.length = length;
this.array = new long[length + 10000];
for (int k = 0; k < length; k++)
{
this.array[k] = k;
}
}
public void Insert (int position, long value)
{
System.Array.Copy(this.array, position, this.array, position + 1, this.length);
this.length++;
this.array[position] = value;
}
}
class Program
{
static void Main (string[] args)
{
ArrayString x = new ArrayString(1000000);
const int K = 1000;
System.DateTime t0 = System.DateTime.UtcNow;
for (int k = 0; k < K; k++)
{
x.Insert(0, 42);
}
System.DateTime t1 = System.DateTime.UtcNow;
double dt = 1000000 * (t1 - t0).TotalSeconds / K;
System.Console.WriteLine("dt = {0} microseconds", dt);
System.Console.ReadLine();
}
}
}
Во вложении проект и бинарь для .Net 3.5
-
dt = 4945,2086 microseconds
win7starter с доступными 2GB RAM
Запускал несколько раз. Результаты приблизительно одинаковы
-
А в списке установленных приложений нашёл что-то вида "Microsoft Net Framework 4 Client Profile"
-
Pentium 4, DDR 400, время = 7'805 микросекунд
-
dt = 4945,2086 microseconds
А память наверное DDR2 800?
-
Хотя, нет Fusion E450 поддерживает DDR3. Остаётся вопрос с частотой...
-
...
И так. Номер буквы - 4 байта, номер атрибутов - 4 байта, итого 8 байтов на символ. Измеряем сколько времени займёт вставка символа в позицию 0 если длина текста 1'000'000 восьмибайтовых символов.
...
Получаем всего лишь 962 микросекунды на Core i7 2600K с памятью DD3 1600 MHz.
Не забываем, что в 2014 появится DDR4 которая раза в два-три быстрее чем DDR3.
А при чем тут быстродействие памяти вообще? У тебя же весь массив (8 мегабайт) в кэш поместился.
У P4 и всяких там Fusion E450 столько кеша нет, потому резко просаживается производительность (в 10 раз).
-
Про точность.
Из всех методов измерения длительности - на моей тачке самый точный Stopwatch
Если выполнить такой код
var sw = Stopwatch.StartNew();
Debug.WriteLine("DateTime.UtcNow.Ticks");
Debug.WriteLine(DateTime.UtcNow.Ticks);
Debug.WriteLine(DateTime.UtcNow.Ticks);
Debug.WriteLine(DateTime.UtcNow.Ticks);
Debug.WriteLine(DateTime.UtcNow.Ticks);
Debug.WriteLine(DateTime.UtcNow.Ticks);
Debug.WriteLine(DateTime.UtcNow.Ticks);
Debug.WriteLine(DateTime.UtcNow.Ticks);
Debug.WriteLine(DateTime.UtcNow.Ticks);
Debug.WriteLine(DateTime.UtcNow.Ticks);
Debug.WriteLine(DateTime.UtcNow.Ticks);
Debug.WriteLine(DateTime.UtcNow.Ticks);
Debug.WriteLine(DateTime.UtcNow.Ticks);
Debug.WriteLine("Environment.TickCount");
Debug.WriteLine(Environment.TickCount);
Debug.WriteLine(Environment.TickCount);
Debug.WriteLine(Environment.TickCount);
Debug.WriteLine(Environment.TickCount);
Debug.WriteLine(Environment.TickCount);
Debug.WriteLine(Environment.TickCount);
Debug.WriteLine(Environment.TickCount);
Debug.WriteLine(Environment.TickCount);
Debug.WriteLine(Environment.TickCount);
Debug.WriteLine(Environment.TickCount);
Debug.WriteLine(Environment.TickCount);
Debug.WriteLine(Environment.TickCount);
Debug.WriteLine(Environment.TickCount);
Debug.WriteLine(Environment.TickCount);
Debug.WriteLine(Environment.TickCount);
Debug.WriteLine(Environment.TickCount);
Debug.WriteLine(Environment.TickCount);
Debug.WriteLine(Environment.TickCount);
Debug.WriteLine("sw.ElapsedTicks");
Debug.WriteLine(sw.ElapsedTicks);
Debug.WriteLine(sw.ElapsedTicks);
Debug.WriteLine(sw.ElapsedTicks);
Debug.WriteLine(sw.ElapsedTicks);
Debug.WriteLine(sw.ElapsedTicks);
Debug.WriteLine(sw.ElapsedTicks);
Debug.WriteLine(sw.ElapsedTicks);
Debug.WriteLine(sw.ElapsedTicks);
Debug.WriteLine(sw.ElapsedTicks);
Debug.WriteLine(sw.ElapsedTicks);
Debug.WriteLine(sw.ElapsedTicks);
Debug.WriteLine(sw.ElapsedTicks);
то результат будет такой
DateTime.UtcNow.Ticks
634671793967968750
634671793967968750
634671793967968750
634671793967968750
634671793967968750
634671793967968750
634671793968125000
634671793968125000
634671793968125000
634671793968125000
634671793968125000
634671793968125000
Environment.TickCount
519301015
519301015
519301015
519301015
519301015
519301015
519301015
519301015
519301015
519301015
519301031
519301031
519301031
519301031
519301031
519301031
519301031
519301031
sw.ElapsedTicks
199727
202547
205395
208358
211166
213921
216699
219554
222412
225179
227929
231585
-
...
И так. Номер буквы - 4 байта, номер атрибутов - 4 байта, итого 8 байтов на символ. Измеряем сколько времени займёт вставка символа в позицию 0 если длина текста 1'000'000 восьмибайтовых символов.
...
Получаем всего лишь 962 микросекунды на Core i7 2600K с памятью DD3 1600 MHz.
Не забываем, что в 2014 появится DDR4 которая раза в два-три быстрее чем DDR3.
А при чем тут быстродействие памяти вообще? У тебя же весь массив (8 мегабайт) в кэш поместился.
У P4 и всяких там Fusion E450 столько кеша нет, потому резко просаживается производительность (в 10 раз).
А может быть спросить у операционной системы размер страницы памяти и... размещать файл на страницах, выстраивая страницы в виде списка (одно/двунаправленного). Страница может быть заполнена полностью или частично. Тогда все сдвиги будут "крошечными"...
-
Хотя, нет Fusion E450 поддерживает DDR3. Остаётся вопрос с частотой...
DDR3 частота 1333. CPU-z показывает 670. Люди подсказали, что ризультат этой программы нужно умножать на 2 (наверное, физики). В итоге и получается где-то 1333. Но, возможно из-за того, что чуть ли не весь комп запихан в один кристалл, контроллер памяти одноканальный.
Насколько я знаю - это существенно.
Но можно попробовать проверить идею Алексея. У меня по 512 КБ на каждое из 2 ядер. Так что можно посмотреть прирост производительности при условии, что строка будет занимать 512 КБ, а не 8 МБ.
-
Хотя, нет Fusion E450 поддерживает DDR3. Остаётся вопрос с частотой...
DDR3 частота 1333. CPU-z показывает 670. Люди подсказали, что ризультат этой программы нужно умножать на 2 (наверное, физики). В итоге и получается где-то 1333. Но, возможно из-за того, что чуть ли не весь комп запихан в один кристалл, контроллер памяти одноканальный.
Насколько я знаю - это существенно.
Но можно попробовать проверить идею Алексея. У меня по 512 КБ на каждое из 2 ядер. Так что можно посмотреть прирост производительности при условии, что строка будет занимать 512 КБ, а не 8 МБ.
Пересылку большого объёма памяти разумнее написать с помощью MMX расширений... Минуя кэши...
-
Пересылку большого объёма памяти разумнее написать с помощью MMX расширений... Минуя кэши...
Вообще через DMA - минуя процессор :-)
-
Но можно попробовать проверить идею Алексея. У меня по 512 КБ на каждое из 2 ядер. Так что можно посмотреть прирост производительности при условии, что строка будет занимать 512 КБ, а не 8 МБ.
Алексей идею Алексея уже проверил :-) . Слегка модифицировав исходник (красным выделены изменения, класс ArrayString остался без изменений):
class Program
{
static void Main (string[] args)
{
for (int size=100000; size<=1000000; size+=100000)
{
ArrayString x = new ArrayString(size);
const int K = 1000;
System.DateTime t0 = System.DateTime.UtcNow;
for (int k = 0; k < K; k++)
{
x.Insert(0, 42);
}
System.DateTime t1 = System.DateTime.UtcNow;
double dt = 1000000 * (t1 - t0).TotalSeconds / K;
System.Console.WriteLine("dt = {0} microseconds; bytes = {3}; longs = {1}; popugai = {2}", dt, size, size/dt, size*8);
x = null;
System.GC.Collect();
}
System.Console.ReadLine();
}
}
Так что теперь замеряем сразу серию. Результаты:
$ mono TestCopy.exe
dt = 170.735 microseconds; bytes = 800000; longs = 100000; popugai = 585.702990013764
dt = 405.835 microseconds; bytes = 1600000; longs = 200000; popugai = 492.811117818818
dt = 1087.669 microseconds; bytes = 2400000; longs = 300000; popugai = 275.819206026834
dt = 3020.222 microseconds; bytes = 3200000; longs = 400000; popugai = 132.440595426429
dt = 5117.21 microseconds; bytes = 4000000; longs = 500000; popugai = 97.709494040698
dt = 6213.729 microseconds; bytes = 4800000; longs = 600000; popugai = 96.5603746156294
dt = 7427.909 microseconds; bytes = 5600000; longs = 700000; popugai = 94.239172827777
dt = 8333.403 microseconds; bytes = 6400000; longs = 800000; popugai = 95.9991974467093
dt = 9388.901 microseconds; bytes = 7200000; longs = 900000; popugai = 95.8578645147073
dt = 10307.17 microseconds; bytes = 8000000; longs = 1000000; popugai = 97.0198415277908
Размер кэша процессора у меня 2 мегабайта:
$ cat /proc/cpuinfo | grep cache
cache size : 2048 KB
cache_alignment : 64
cache size : 2048 KB
cache_alignment : 64
И явно видно, что попугаи после пересечения барьера в 2 мегабайта массива, стремительно начинают вымирать. Вымирают правда не все, и начиная с 4 мегабайт и выше популяция попугаев стабильно неизменна.
К чему это я?.. А! К тому, что в реальном текстовом редакторе кэш будет инвалидироваться реально часто, например после вызовов функций ядра (захотели скажем перерисовать окошко после того как ткнули в кнопку), либо просто графических либ (которые радостно выкинут из кеша этот текст, и засунут туда, скажем, битмапы отрендеренных шрифтов).
-
Пересылку большого объёма памяти разумнее написать с помощью MMX расширений... Минуя кэши...
Вообще через DMA - минуя процессор :-)
Кто же пустит работать с DMA... это надо иметь доступ на нулевой уровень защиты процессора, то есть, либо внедриться в ядро ОС, либо написать свою ОС... :) А регистры MMX, равно как и регистры сопроцессора доступны любой программе.
Была где-то статья AMD, где сравнивались скорости разных способов копирования памяти, обычной пересылкой (rep movs), через регистры MMX, через регистры сопроцессора, prefetch и пр. Если отбросить prefetch, то через регистры MMX/сопроцессора копирование происходит быстрее всего.
Но оптимальным было бы хранение текста на страницах... Исчезла бы зависимость от размера текстового файла, любой сдвиг затрагивал бы не более 2-х страниц.
-
Кто же пустит работать с DMA... это надо иметь доступ на нулевой уровень защиты процессора, то есть, либо внедриться в ядро ОС, либо написать свою ОС... :) А регистры MMX, равно как и регистры сопроцессора доступны любой программе.
Была где-то статья AMD, где сравнивались скорости разных способов копирования памяти, обычной пересылкой (rep movs), через регистры MMX, через регистры сопроцессора, prefetch и пр. Если отбросить prefetch, то через регистры MMX/сопроцессора копирование происходит быстрее всего.
Но оптимальным было бы хранение текста на страницах... Исчезла бы зависимость от размера текстового файла, любой сдвиг затрагивал бы не более 2-х страниц.
Тут такая штука - MMX на современном процессоре может и не быть.
-
Еще пара ссылок в тему:
http://www.catch22.net/tuts/neatpad/17 (http://www.catch22.net/tuts/neatpad/17)
http://www.cs.unm.edu/~crowley/papers/sds/sds.html (http://www.cs.unm.edu/~crowley/papers/sds/sds.html)
-
Про точность. Из всех методов измерения длительности - на моей тачке самый точный Stopwatch
Для измерения точного монотонного времени написал класс:
public static class Clock
{
public static double GetSeconds ();
}
Возвращает количество секунд прошедшее с момента старта программы (точнее с момента инициализации статического класса Clock, но он инициализируется в main).
Он имеет следующую реализацию
Под виндой:
private static class Windows_PerformanceCounter
{
[System.Runtime.InteropServices.DllImport("kernel32.dll")]
private static extern int QueryPerformanceFrequency (out long frequency);
[System.Runtime.InteropServices.DllImport("kernel32.dll")]
private static extern int QueryPerformanceCounter (out long counter);
private static readonly double scale, offset;
static Windows_PerformanceCounter ()
{
long frequency;
QueryPerformanceFrequency(out frequency);
if (frequency > 0)
{
scale = 1.0 / frequency;
long count;
QueryPerformanceCounter(out count);
offset = scale * count;
}
}
public static double GetSeconds ()
{
long count;
QueryPerformanceCounter(out count);
return scale * count - offset;
}
}
Под Линуксом:
private static class Unix_librt
{
private const int CLOCK_MONOTONIC = 1;
private struct Time
{
public uint seconds;
public uint nanoseconds;
}
[System.Runtime.InteropServices.DllImport("/lib/librt.so.1")]
private static extern int clock_gettime (int clockId, ref Time time);
private static double offset;
public static double GetSeconds ()
{
Time t = new Time();
clock_gettime(CLOCK_MONOTONIC, ref t);
return t.seconds + 0.000000001*t.nanoseconds - offset;
}
static Unix_librt ()
{
offset = GetSeconds();
}
}
Точность от 200 нс до 1400 нс в зависимости от компьютера (от часов в чиспете). 200 нс было на каком-то современном ксеонистом 16 ядерном серваке, а 1400 на каком-то старом компьютере времён Pentium 4.
Кстати под Линуксом System.DateTime.UtcNow имеет такую же высокую точность, но имеет недостаток -- не монотонен (зависит от перевода часов).
-
Для измерения точного монотонного времени написал класс:
Под Линуксом не знаю, а под Виндой Stopwatch так и работает. Вот кусок из него (получено Reflector'ом):
public static long GetTimestamp()
{
if (IsHighResolution)
{
long num = 0L;
SafeNativeMethods.QueryPerformanceCounter(out num);
return num;
}
return DateTime.UtcNow.Ticks;
}
-
Сейчас измерил на современном компьютере время вставки элемента в массив -- оно ничтожно. Поэтому для представления текста на современном компьютере уже не нужны никакие там сложные структуры, а достаточно взять просто массив символов. Вставляешь символ -- тупо сдвигаешь все последующие символы на одну позицию и не паришься на счёт того, что это якобы медленно. Уже не медленно!!!
Если уж пример на C#, то там для этого есть более эффективный метод - Array.Copy(...)
Оказывается, есть еще эффективнее - класс Buffer (http://msdn.microsoft.com/ru-ru/library/system.buffer.aspx). "This class provides better performance for manipulating primitive types than similar methods in the System.Array class".
-
Оказывается, есть еще эффективнее - класс Buffer (http://msdn.microsoft.com/ru-ru/library/system.buffer.aspx)
Несколько лет назад я их мерил. Для крохотных массивов побеждает for. Для средненьких массивов вперёд вырывается System.Buffer. Затем, при дальнейшем увеличении размера массива разница между System.Buffer и System.Array стремится к нулю.
-
Насколько существенен отрыв (а также , какова оценка "среднего" диапазона, т.е скажем так каков диапазон для 5 кратного превосходства)
-
Насколько существенен отрыв (а также , какова оценка "среднего" диапазона, т.е скажем так каков диапазон для 5 кратного превосходства)
Разница не так велика. А диапазоны сильно зависят от размеров кэшей процессора первого, второго и третьего уровней. Ещё конечно есть разница между for побайтовым и for по Int64 и по более толстым структурам (кэш линейка раньше была 32 байта, а на современных процессорах наверное больше, вот for по структурам размером с кэш-линейку работает быстро). А для очень больших массивов всё выходит примерно на одну асимптотику.
-
Понятно - сильная завязка на реализацию и железо...т.е к использованию только когда это РЕАЛЬНО :) необходимо.
-
Пост по теме: http://habrahabr.ru/post/197650/