Хабр Курсы для всех
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 122
А B-Tree почему не стали рассматривать?
List и Array на таких гигантских размерах стопудово попадут в LOH, устроят там междусобойчик, и OutOfMemory наступит гораздо раньше…
List и Array на таких гигантских размерах стопудово попадут в LOH, устроят там междусобойчик, и OutOfMemory наступит гораздо раньше…
Тут возникает вопрос: сколько мы потратим памяти на организацию дерева?
А еще у великого и могучего Джефри Рифтера есть приколюха Wintellect Power Collections, и там есть BigList и другие радости .
А вообще используйте SQL Server. Он все равно все в память выгружает.
А вообще используйте SQL Server. Он все равно все в память выгружает.
Отличная статья! Хоть кто-то в наше время заботится об оптимизации памяти!
Спасибо за статью. Как раз собираемся стартовать проект, в котором подобная задача, скорее всего, будет. Одной проблемой меньше :) Очень благодарен.
хм. скажите, а использование хэширования FNV [модификацированного] чем-то мотивировано? [Skeet, Bernstein того же порядка по вычислительной сложности; более прожорливые, например ELF, вохможно дали бы лучшее распределение]. или же FNV выбирался из ряда и показал себя наиприемлемейшим на вашем наборе данных?
Мда уж… Вот вам и высокоуровневость. Хых. А что, не судьба, в том же массиве устроить сортировку пирамидкой, а потом искать по самому ключу, без всяких хэшей за log(N)? Сложности и кода было бы раз в 10 меньше.
Вот и попробуйте потом мне доказать, что программировать на C# проще, чем на Си, зная пару-тройку стандартных алгоритмов из Кнута.
Вот и попробуйте потом мне доказать, что программировать на C# проще, чем на Си, зная пару-тройку стандартных алгоритмов из Кнута.
Мы не можем разместить все данные одним массивом. В этом вся проблема.
Так тут же не важно, сколько массивов вы выделите. Можно сделать и 10 массивов по 10 миллионов записей, и две функции get(i), set(i), которые по индексу выбирают нужный массив. И это не помешает построить пирамиду на этих нескольких массивах.
А вообще, можно ещё порекомендовать Вам разбить ваше множество ключей на несколько подмножеств, которые, например, определяются первыми четырьмя байтами ключа. Тогда, глядишь, и SQL с поиском справится.
А вообще, можно ещё порекомендовать Вам разбить ваше множество ключей на несколько подмножеств, которые, например, определяются первыми четырьмя байтами ключа. Тогда, глядишь, и SQL с поиском справится.
Такие объемы данных вы будете очень долго сортировать, а поиск ключа в хеш-таблице не зависит от её размера. Кнута вы не дочитали, похоже. Сравнение C# с C тут вообще неуместно.
Так я зря что ли про пирамидальную сортировку написал? Данные будут загружаться O(C * N) времени. Пирамидальная сортировка осуществляется за O(log(N) * N) операций. В итоге, всё это будет сложнее всего в log(N) раз, при N = 10 ^ 8 этот коэффицент будет примерно 25. При чём, это 25 в пересчёте на быстрые операции доступа в память. Коэффицент C — время, требующееся для загрузки одного значения извне, сильно больше. А пирамидальную сортировку можно проводить инкрементально: загрузили одно значение, вставили его на нужное место. Затраты на сортировку будут не заметны.
Скорость работы хэшей, особенно, если под каждый элемент выделять память, может быть существенно меньше. Операции выделения памяти — не бесплатные, и чем больше элементов памяти выделяется, тем дольше они работают. Плюс равномерность никто не гарантирует, вполне может быть так, что в некоторх местах хэш-таблицы будут длинные списки со сталкивающимися элементами. Но даже если и равномерно всё будет… Какой длины будет список для некоторого значения хэша? Чтобы добиться той же сложности поиска log(n) ~ 25, нужно будет делать таблицу шириной 10000000/25 = на 4000000 указателей.
Да и вообще, мы проверяли просто тупо. Красно-чёрные деревья, например, работают в среднем быстрее, чем хэш-таблицы, использовавшиеся в 2008 году в Perl. Хоть там и вставка идёт за 2*log(N), и поиск такой же. НО, хэш ещё нужно посчитать, и пока он считается мы уже успевали по 256-битному ключу найти нужное место в дереве. Дальше мы подтормаживали со вставкой, потому что дерево нужно было поворачивать. Но потом существенно выигрывали на поиске, потому что, опять же, за время подсчёта хэша и прохода по списку соответствующему, мы уже находили 2-3 нужных значения.
Поэтому, если поиск осуществляется чаще, чем появляются новые данные, лучше использовать деревянные структуры.
Скорость работы хэшей, особенно, если под каждый элемент выделять память, может быть существенно меньше. Операции выделения памяти — не бесплатные, и чем больше элементов памяти выделяется, тем дольше они работают. Плюс равномерность никто не гарантирует, вполне может быть так, что в некоторх местах хэш-таблицы будут длинные списки со сталкивающимися элементами. Но даже если и равномерно всё будет… Какой длины будет список для некоторого значения хэша? Чтобы добиться той же сложности поиска log(n) ~ 25, нужно будет делать таблицу шириной 10000000/25 = на 4000000 указателей.
Да и вообще, мы проверяли просто тупо. Красно-чёрные деревья, например, работают в среднем быстрее, чем хэш-таблицы, использовавшиеся в 2008 году в Perl. Хоть там и вставка идёт за 2*log(N), и поиск такой же. НО, хэш ещё нужно посчитать, и пока он считается мы уже успевали по 256-битному ключу найти нужное место в дереве. Дальше мы подтормаживали со вставкой, потому что дерево нужно было поворачивать. Но потом существенно выигрывали на поиске, потому что, опять же, за время подсчёта хэша и прохода по списку соответствующему, мы уже находили 2-3 нужных значения.
Поэтому, если поиск осуществляется чаще, чем появляются новые данные, лучше использовать деревянные структуры.
Круто расписали, мне нечего возразить.
Честно говоря не сталкивался с пирамидальной сортировкой, но бегло прбежав описание засомневался. Если только там нужны перемещения между массивами, то это затраты на копирование памяти, я к тому, что в .Net вставка нового элемента в массив — это создание нового массива на 1 больше, копирование туда старого и только тога вставка (не важно в какую часть — в конец или середину). Не совсем понял сколько тянет инфраструктура самого дерева. Да и фразы «на почти отсортированных массивах работает столь же долго, как и на хаотических данных» не вдохновляют, тем более, что вы собираетесь сортировать после каждой вставки. Не понял фразы «скорость работы хэшей, особенно, если под каждый элемент выделять память, может быть существенно меньше» — память под занчение нужно выделять в любом случае, а хешсегмент фиксирован. «Поэтому, если поиск осуществляется чаще...» — в нашем случае нужно расчитывать на 1-разовую вставку 100 млн. и одноразовый поиск среди других 100 млн., поэтому поиск не чаще и даже наоборот — вставляться как правило будет на половину меньше, а сравниваемая сторона всегда окло 100 млн. и все время растет.
1. У Вас структура небольшая, поэтому будет копироваться очень быстро. Код копирования в MS очень хорошо оптимизирован, поэтому он всё сделает за 4 инструкции = 2 чтения + 2 записи.
2. Речь про выделение памяти вот в каком контексте: либо под каждый элемент выделать память заново, либо сразу выделить большой массив под несколько миллионов записей. Второе осуществится быстрее.
3. Особенность пирамиды (или другое название — куча) в том, что вставка нового элемента в неё занимает O(log N) времени. То есть, если Вы хотите добавить в массив размером N ещё M элементов, то сложность будет O(log(N + M) * M).
4. Таким образом, если: 4.1 у вас множество только лишь растёт; 4.2 вставки происходят реже, чем просмотр — то пирамида будет эффективнее хэша за счёт экономии на операциях выделения памяти (при вставке), просмотре списков и расчёте хэша (при поиске).
5. Вот если бы Вам нужно было удалять элементы, тогда да, дерево или хэш были предпочтительны. Но в этой задаче, как я понял, информация только лишь накапливается.
2. Речь про выделение памяти вот в каком контексте: либо под каждый элемент выделать память заново, либо сразу выделить большой массив под несколько миллионов записей. Второе осуществится быстрее.
3. Особенность пирамиды (или другое название — куча) в том, что вставка нового элемента в неё занимает O(log N) времени. То есть, если Вы хотите добавить в массив размером N ещё M элементов, то сложность будет O(log(N + M) * M).
4. Таким образом, если: 4.1 у вас множество только лишь растёт; 4.2 вставки происходят реже, чем просмотр — то пирамида будет эффективнее хэша за счёт экономии на операциях выделения памяти (при вставке), просмотре списков и расчёте хэша (при поиске).
5. Вот если бы Вам нужно было удалять элементы, тогда да, дерево или хэш были предпочтительны. Но в этой задаче, как я понял, информация только лишь накапливается.
Мы не знаем сколько будет данных, может 1 тыс., может 100 млн., поэтому память заранее выделяем лишь с небольшим запасом (параметр линейного роста листов в статье). Если памяти много, можем этим параметром выделить очень большой запас, в результате ( в идеале) каждая цепочка выделится 1 раз и затем свернётся по факту в конце. Т.е. проблем со вставкой я здесь не вижу.
А вот с поиском даже спорить не буду. Тут сделано очень просто в угоду экономии памяти. Я понимаю, что есть более выгодные поисковые структуры. Можно вас попросит, если вы имеете такой опыт, прикинуть сколько будет занимать памяти организация инфраструктуры пирамиды? И как вы предполагали делать поиск после сортировки, бинарно или как?
А вот с поиском даже спорить не буду. Тут сделано очень просто в угоду экономии памяти. Я понимаю, что есть более выгодные поисковые структуры. Можно вас попросит, если вы имеете такой опыт, прикинуть сколько будет занимать памяти организация инфраструктуры пирамиды? И как вы предполагали делать поиск после сортировки, бинарно или как?
Я тут попробовал порешать задачу из статьи на C#, чтобы прочувствовать проблему.
Сразу решил обходиться без unsafe и написания собственных хэштаблиц, сортировок, итп. То есть использовать имеющиеся в стандартных библиотеках реализации.
Сразу скажу, ваше предложение использовать дерево — неэффективно по памяти из-за указателей.
Самый эффективный по памяти и простой по коду вариант — положить всё в массив (использовал несколько массивов, т.к. в .NET ограничен размер одного куска памяти на 2gb), применить Array.Sort (сортировка 1млн записей заняла 14 минут на Athlon X2 2.7 Ghz. Алгоритм QuickSort там). Потом использовать Array.BinarySearch. 2.4 гб памяти съело при работе.
Самый быстрый вариант — хэштаблица (опять же, несколько). Отдельная структура для ключа (вместо byte[16] я использовал два Int64, чтобы не использовать unsafe), отдельная структура для значений. Понадобилось 3.6 гигабайта памяти. У меня только 4 гб, поэтому часть хэштаблиц засвопилось, и всё стало тормозить. Для сравнения скорости я протестировал на половине объема (50млн). Хэширование заняло 20 секунд.
Сразу решил обходиться без unsafe и написания собственных хэштаблиц, сортировок, итп. То есть использовать имеющиеся в стандартных библиотеках реализации.
Сразу скажу, ваше предложение использовать дерево — неэффективно по памяти из-за указателей.
Самый эффективный по памяти и простой по коду вариант — положить всё в массив (использовал несколько массивов, т.к. в .NET ограничен размер одного куска памяти на 2gb), применить Array.Sort (сортировка 1млн записей заняла 14 минут на Athlon X2 2.7 Ghz. Алгоритм QuickSort там). Потом использовать Array.BinarySearch. 2.4 гб памяти съело при работе.
Самый быстрый вариант — хэштаблица (опять же, несколько). Отдельная структура для ключа (вместо byte[16] я использовал два Int64, чтобы не использовать unsafe), отдельная структура для значений. Понадобилось 3.6 гигабайта памяти. У меня только 4 гб, поэтому часть хэштаблиц засвопилось, и всё стало тормозить. Для сравнения скорости я протестировал на половине объема (50млн). Хэширование заняло 20 секунд.
Тут важно, что нужно делать именно пирамиду. Вообще, QuickSort в худшем случае имеет сложность O(N^2), и им нельзя сортировать с постепенным накоплением данных. А вообще, интересно… Попробую тоже сделать сортировку. Вы rand'омом заполняли?
Разбивать на простые типы идея правильная, но у нас 16 — это максимальная длина, внутри этого буфера хранится ключ фиксированной длины и дальше довесок с нуль-терминатором. Короче, задача универсальнее чем то что я описал в статье. Поэтому искал способ работы масивом.
Вопрос по поводу нескольких хештаблиц: получается что для поиска нужно обойти все таблицы, и каждая будет вычислять хеш? Т.е. мне интерессно сколько было таблиц и сколько при такой организации займет поиск. Если так прикинуть, что там хешсегмент 1:1 (400 Мб), что и дает такую скорость + избыток 8 Б на вхождение (800 Мб) = 1200 Мб. Я так понимаю вы заранее заказывали ёмкость словаря, чем обошли проблему двукратного роста. Вот и вышло 2,4 + 1,2 = 3,6.
Вопрос по поводу нескольких хештаблиц: получается что для поиска нужно обойти все таблицы, и каждая будет вычислять хеш? Т.е. мне интерессно сколько было таблиц и сколько при такой организации займет поиск. Если так прикинуть, что там хешсегмент 1:1 (400 Мб), что и дает такую скорость + избыток 8 Б на вхождение (800 Мб) = 1200 Мб. Я так понимаю вы заранее заказывали ёмкость словаря, чем обошли проблему двукратного роста. Вот и вышло 2,4 + 1,2 = 3,6.
Да. И не забываем про сборщик мусора: чем меньше объектовы выделено, тем меньше он тормозит.
Вот и попробуйте потом мне доказать, что программировать на C# проще, чем на Си, зная пару-тройку стандартных алгоритмов из Кнута.
Вам правда каждый день нужно работать с такими объемами данных?
А дело не в объёмах данных. Просто стиль мышления в C# склоняет к сложным решениям относительно несложных задачек. Простые какие-нибудь задачки в C# народ тоже решает, левой пяткой в правом ухе ковыряясь. Просто реальный вот пример. Делаем мы язык программирования, там есть лексическй анализатор. У меня на Си он вышел короче, чем у коллеги на C#, да ещё и работает быстрее, и может больше… И это с у чётом того, что я ещё собственные контейнеры написал, а друг пользовался стандартным словарём.
И я вот не понимаю, так в чём же выгода от этого самого C#?
И я вот не понимаю, так в чём же выгода от этого самого C#?
Все дело в том, что C и C# решают разные задачи. Не думаю, что у вас выйдет на C так же быстро, просто и элегантно распарсить XML, организовать ORM или написать веб-приложение. Также не забываем про безопасную память.
Да запросто. Библиотек, парсящих XML для Си написано много. Но при этом, нужно учитывать, что XML в большинстве случаев — это overkill.
Ок, XML — не самый лучший пример. В любом случае, используя C сталкиваешься со множеством совершенно «бытовых» проблем. Многие из них решены в C++, однако не все.
Мой тезис таков: если пытаться писать на Си, как на Java, то, естественно, вылезет куча проблем. И печально видеть, как люди георически с ними борятся. Но если писать на Си, как на Си, то всё вполне удобно.
В Си, конечно, можно было бы кое-что подправить и кое-что изменить, и кое-какими современными средствами оснастить его, чтобы стало ещё удобнее… Но это точно не ООП-шными примочками, которые разрушают концептуальную простоту Си.
Хм. Я вот поэтому и не люблю Java и C# — они языкотворчество куда-то совсем не туда по моим представлениям ведут: создают дополнительные ограничения, забирают производительность, и выезжают, такое ощущение, что на не совсем честном PR'е. Недавняя история: SUN как-то вывесила у себя на сайте огромный баннер с рекламой 'Java goes to Mars', на которой был изображён марсаход, и типа вот в нём работает JME. Фанаты сразу оживились, один мой знакомый даже категорически перешёл на Java, из-за её внеземной крутости… А потом в интервью один из программистов проекта сообщил, что фига вам, на марсоходах стоит кастомная OS реально времени, всё под неё пишется на Си, а Java в центре управления они предпочитают Python.
Вот, как-то так. Поэтому я всегда и пишу, что не понимаю, зачем нужны языки вроде Java и C#.
В Си, конечно, можно было бы кое-что подправить и кое-что изменить, и кое-какими современными средствами оснастить его, чтобы стало ещё удобнее… Но это точно не ООП-шными примочками, которые разрушают концептуальную простоту Си.
Хм. Я вот поэтому и не люблю Java и C# — они языкотворчество куда-то совсем не туда по моим представлениям ведут: создают дополнительные ограничения, забирают производительность, и выезжают, такое ощущение, что на не совсем честном PR'е. Недавняя история: SUN как-то вывесила у себя на сайте огромный баннер с рекламой 'Java goes to Mars', на которой был изображён марсаход, и типа вот в нём работает JME. Фанаты сразу оживились, один мой знакомый даже категорически перешёл на Java, из-за её внеземной крутости… А потом в интервью один из программистов проекта сообщил, что фига вам, на марсоходах стоит кастомная OS реально времени, всё под неё пишется на Си, а Java в центре управления они предпочитают Python.
Вот, как-то так. Поэтому я всегда и пишу, что не понимаю, зачем нужны языки вроде Java и C#.
Может все же расскажете, в какой области лежат ваши программистские интересы? Какие задачи вы решаете?
Два класса. 1. Вычислительные: математическое моделирование и распознавание образов, обычно, с требованиями высокой производительности, так что в ход идут GPU и кластеры из многопроцессорные машин. 2. Системные: работаю над протоколами передачи данных, средами для поддержки больших вычислений, языком программирования, операционкой. Один из плюсов работы в РАН — можно в разнообразных проектах участвовать.
Может, проблема тут не в C#, а в вашем коллеге?
Что может C, чего не может C#, и что позволяет сделать лексический анализатор короче по коду?
Что может C, чего не может C#, и что позволяет сделать лексический анализатор короче по коду?
То, что C# склоняет к наворачиванию сложной системы типов вокруг задачи. Главный лозунг ООП — плоди классы на каждый чих. Вот человек и наплодил. И это не проблема моего конкретного коллеги, так пишутся почти все программы на C#/Java. Я как-то ползал по GitHub'у и смотрел. Может, конечно, есть и другие примеры, но я их не встречал.
Вот. А один мудрый человек сказал: лучше иметь десять типов данных и сто функций, чем сто типов данных и 10 функций. Это хороший принцип, он действительно помогает… C# (как представитель ООП) склоняет к противоположному. А в худших случаях это ещё и выливается в 100 типов данных и 100 функций.
Коллега наплодил около десятков классов, чтобы представлять различные сущности возникающие при разборе… Я же не плодил ничего, потому что моя программа делает одну простую вещь — разбирает буфер с исходным текстом, когда встречает токен, она его выдаёт и запоминает, если это идентификатор. У него же там какие-то навороченные курсоры, классы для токенов, классы для классов токенов, ну и т.д.
Вот. А один мудрый человек сказал: лучше иметь десять типов данных и сто функций, чем сто типов данных и 10 функций. Это хороший принцип, он действительно помогает… C# (как представитель ООП) склоняет к противоположному. А в худших случаях это ещё и выливается в 100 типов данных и 100 функций.
Коллега наплодил около десятков классов, чтобы представлять различные сущности возникающие при разборе… Я же не плодил ничего, потому что моя программа делает одну простую вещь — разбирает буфер с исходным текстом, когда встречает токен, она его выдаёт и запоминает, если это идентификатор. У него же там какие-то навороченные курсоры, классы для токенов, классы для классов токенов, ну и т.д.
Это вопрос в подходе. Как в C, так и в C# можно решать конкретную прикладную задачу, а можно пытаться сделать «универсально, с заделом на будущее». Ну и over-engineering — тоже косяк разработчика/архитектора.
У меня прямо противоположный опыт. Человек на С нагородил поинтеров, reference counter-ов и прочей херни. Потом, когда прога стала личить память непонятно по какому чиху, полгода сидел отлаживал. И насколько я знаю, проблема до сих пор не найдена. Фантомная ошибка. Welcome to the real world, Neo :)
Уже только из-за этого на шарпе можно сэкономить уйму времени. Не говоря уже о таких вкусностях как Expression.Compile() и т.д.
Забавно выглядит то, как на С живой код генерить? :)
Уже только из-за этого на шарпе можно сэкономить уйму времени. Не говоря уже о таких вкусностях как Expression.Compile() и т.д.
Забавно выглядит то, как на С живой код генерить? :)
Друг, генерил .cpp'шник и отдавал на вход компилятору, затем выдирал из exe'шника нужный кусок кода, загружал в свою область памяти, правил смещения и передавал на выполнение)
Но это малоприменимо конечно, гораздо более распрастраненный кейс (если так вообще можно говорить про генерацию кода на лету в C++) — писать в память машкодами :)
А Expression.Compile ведь тоже появился далеко не сразу в .NETпервые 8 лет существования платформы, эмитили MSIL :) Да и сейчас Expression.Compile решает не все задачи и не всегда самым удобным образом, так что lightweight code generation еще никто не отменял в 3-их и 4-ых дотнетах.
Но это малоприменимо конечно, гораздо более распрастраненный кейс (если так вообще можно говорить про генерацию кода на лету в C++) — писать в память машкодами :)
А Expression.Compile ведь тоже появился далеко не сразу в .NETпервые 8 лет существования платформы, эмитили MSIL :) Да и сейчас Expression.Compile решает не все задачи и не всегда самым удобным образом, так что lightweight code generation еще никто не отменял в 3-их и 4-ых дотнетах.
Так когда человек городит поинтеры и (о боже, ужасный ужас) reference counter'ы, это как раз и означает, что не ведает он о творимом зле. reference counter'ы свидетельствуют лишь о том, что человек пытался писать, как на Java: типа есть у нас объекты, живущие богатой внутренней жизнью, и пребывающие в сложных ссылочных связях. Для этого, конечно, нужно считать ссылки, чтобы всё не развалилось. Но это не нормальный подход к Си. Если бы человек подумал, какие массивы и структуры данных ему нужны, и какой код будет выполняться вокруг них, то подобных проблем не возникло бы.
Да, иногда приходится считать ссылки, когда, например, по каким-то причинам у нас в распоряжении есть только нити, и нет лёгких процессов, и когда некоторые нити занимаются вводом-выводом, да ещё и асинхронно, нужно считать. Но это нужно редко, и техника вполне стандартная, и подсчёт ссылок можно вообще засунуть в одну функцию.
Многонитевое программирование в Си — это, конечно, большая проблема. Но проблема не языка, а программистов, которые забывают простой принцип не плодить лишние сущности сложности. Да и просто от недостатка образования и опыта в этой области… Пишут, например, какие-нибудь свои корявые очереди сообщений, боятся данные копировать между нитями, потому что общая память же, и типа, я лучше наворочу 10 указателей, чем 20 байтов скопирую. Не умеют асинхронный ввод/вывод использовать. Не пользуются протонитями… В общем, вот.
Вроде, кажется, что Java или C# за них решает эти проблемы, но вот ничего подобного. И память так же течёт (потому что нити зависли в deadlock'ах, и не освобождают ресурсы), и сборщики мусора начинают всё тормозить, и ввод-вывод тормозит из-за непродуманности. В Си-то хоть эти проблемы все сразу же наружу вылезают, и либо ошибка исправляется, либо к программисту приходит просветление и он понимает, как сделать проще. А в Java/C# это всё скрыто, и вроде как работает, пока, например, через месяц не обнаруживается, что рабочий заниамет 50GiB виртуальной памяти.
Expession.Compile, конечно, в Си не хватает. Да и много чего не хватает, на самом деле. Есть проблемы с обработкой ошибок, с нетривиальностью написания generic-кода, с невозможность задавать свои control-flow структуры, что полезно во многих случаях и так далее. Много проблем. Поэтому мы и разрабатываем новый язык программирования с блэкджеком и замыканиями: )
Но в Java и C# проблем ещё больше, хоть они и не видны программисту снаружи, внутри там куча косяков. Вероятно, расчёт такой, что никто разбираться не будет, и внешней, кажущейся беспроблемности для среднестатистического программиста и менеджера вполне будет достаточно. Ну… А потом растить большую и толстую экосистему, приносящую денюжку, вокруг этих платформ. В принципе, вокруг Си тоже экосистема растёт, но… Вроде как, она какая-то более честная, что ли. Во времена её зарождения маркетологов в IT было меньше, больше было учёных и инженеров.
Да, иногда приходится считать ссылки, когда, например, по каким-то причинам у нас в распоряжении есть только нити, и нет лёгких процессов, и когда некоторые нити занимаются вводом-выводом, да ещё и асинхронно, нужно считать. Но это нужно редко, и техника вполне стандартная, и подсчёт ссылок можно вообще засунуть в одну функцию.
Многонитевое программирование в Си — это, конечно, большая проблема. Но проблема не языка, а программистов, которые забывают простой принцип не плодить лишние сущности сложности. Да и просто от недостатка образования и опыта в этой области… Пишут, например, какие-нибудь свои корявые очереди сообщений, боятся данные копировать между нитями, потому что общая память же, и типа, я лучше наворочу 10 указателей, чем 20 байтов скопирую. Не умеют асинхронный ввод/вывод использовать. Не пользуются протонитями… В общем, вот.
Вроде, кажется, что Java или C# за них решает эти проблемы, но вот ничего подобного. И память так же течёт (потому что нити зависли в deadlock'ах, и не освобождают ресурсы), и сборщики мусора начинают всё тормозить, и ввод-вывод тормозит из-за непродуманности. В Си-то хоть эти проблемы все сразу же наружу вылезают, и либо ошибка исправляется, либо к программисту приходит просветление и он понимает, как сделать проще. А в Java/C# это всё скрыто, и вроде как работает, пока, например, через месяц не обнаруживается, что рабочий заниамет 50GiB виртуальной памяти.
Expession.Compile, конечно, в Си не хватает. Да и много чего не хватает, на самом деле. Есть проблемы с обработкой ошибок, с нетривиальностью написания generic-кода, с невозможность задавать свои control-flow структуры, что полезно во многих случаях и так далее. Много проблем. Поэтому мы и разрабатываем новый язык программирования с блэкджеком и замыканиями: )
Но в Java и C# проблем ещё больше, хоть они и не видны программисту снаружи, внутри там куча косяков. Вероятно, расчёт такой, что никто разбираться не будет, и внешней, кажущейся беспроблемности для среднестатистического программиста и менеджера вполне будет достаточно. Ну… А потом растить большую и толстую экосистему, приносящую денюжку, вокруг этих платформ. В принципе, вокруг Си тоже экосистема растёт, но… Вроде как, она какая-то более честная, что ли. Во времена её зарождения маркетологов в IT было меньше, больше было учёных и инженеров.
Попробую без купюр указать плюсы и минусы С#:
— вуаль вирутальной машины — что там происходит, только Майкрософту изветсно
— тормознутые визуальные библиотеки
— местами вознакают сомнения в лаконичности архитектуры — не поймешь чего больше, то ли правил, то ли исключений из правил
— создает кашу из старых и новых библиотек, где уже ноги можно поломать тут тебе Generic версии и не Generic и что использовать не всегда понятно. Чего стоит разобраться в надцати коллекций.
— скорость меньше чем у нативного кода
…
+ кроссплатформенность — если оно собралось и работает, скорее всего оно будет работать везде где есть эта версия .Net — остальное проблема Майкрософт (я не учитываю инфоки платформы и прочие не кроссплатформенные вещи)
+ у вас не будет проблем с утечкой памяти на таком уровне как это возможно на нейтиве
+ RTTI — рефлексия, это кул и позволяет очень много. Декларативное програмирование.
+ возможность использовать для десктопных, мобильных и веб приложений (включая клиентские)
+ большое количество библиотек
+ развитие семимильными шагами
…
— вуаль вирутальной машины — что там происходит, только Майкрософту изветсно
— тормознутые визуальные библиотеки
— местами вознакают сомнения в лаконичности архитектуры — не поймешь чего больше, то ли правил, то ли исключений из правил
— создает кашу из старых и новых библиотек, где уже ноги можно поломать тут тебе Generic версии и не Generic и что использовать не всегда понятно. Чего стоит разобраться в надцати коллекций.
— скорость меньше чем у нативного кода
…
+ кроссплатформенность — если оно собралось и работает, скорее всего оно будет работать везде где есть эта версия .Net — остальное проблема Майкрософт (я не учитываю инфоки платформы и прочие не кроссплатформенные вещи)
+ у вас не будет проблем с утечкой памяти на таком уровне как это возможно на нейтиве
+ RTTI — рефлексия, это кул и позволяет очень много. Декларативное програмирование.
+ возможность использовать для десктопных, мобильных и веб приложений (включая клиентские)
+ большое количество библиотек
+ развитие семимильными шагами
…
— вуаль вирутальной машины — что там происходит, только Майкрософту изветсно
Только МС и всем тем, кто может в студии галочку выставить, чтобы ASM показывало
— тормознутые визуальные библиотеки
Ну не знаю, что у вас тормозит. WinForms — летает, WPF на железе 2005 года — летает, SL — тоже все летает, если руки правильно заточены.
— местами вознакают сомнения в лаконичности архитектуры — не поймешь чего больше, то ли правил, то ли исключений из правил
Это проблема всех проектов, где работает больше 1 человека.
— создает кашу из старых и новых библиотек, где уже ноги можно поломать тут тебе Generic версии и не Generic и что использовать не всегда понятно. Чего стоит разобраться в надцати коллекций.
О каких коллекциях конкретно идет речь? Если надо список — ListOfT, надо множество HashSetOfT, надо hash-based словарь — DictionaryOfKV, надо red-black-tree — SortedDictionaryOfKV, надо bindable коллекцию — ObservableCollectionOfT. У каждой коллекции свои плюсы и минусы, и их, как уважающему себя человеку, надо знать.
— скорость меньше чем у нативного кода
Скорость разработки или скорость выполнения конкретных методов?
Только МС и всем тем, кто может в студии галочку выставить, чтобы ASM показывало
— тормознутые визуальные библиотеки
Ну не знаю, что у вас тормозит. WinForms — летает, WPF на железе 2005 года — летает, SL — тоже все летает, если руки правильно заточены.
— местами вознакают сомнения в лаконичности архитектуры — не поймешь чего больше, то ли правил, то ли исключений из правил
Это проблема всех проектов, где работает больше 1 человека.
— создает кашу из старых и новых библиотек, где уже ноги можно поломать тут тебе Generic версии и не Generic и что использовать не всегда понятно. Чего стоит разобраться в надцати коллекций.
О каких коллекциях конкретно идет речь? Если надо список — ListOfT, надо множество HashSetOfT, надо hash-based словарь — DictionaryOfKV, надо red-black-tree — SortedDictionaryOfKV, надо bindable коллекцию — ObservableCollectionOfT. У каждой коллекции свои плюсы и минусы, и их, как уважающему себя человеку, надо знать.
— скорость меньше чем у нативного кода
Скорость разработки или скорость выполнения конкретных методов?
— Только МС и всем тем, кто может в студии галочку выставить, чтобы ASM показывало
Есть реальный опыт, чем можете поделитсья?
— WinForms — летает
Жутко тормозит даже на современном железе, многие жалуются. Поставьте бекграунд на форме, гриду с парой десятком колонок, якоря и увидите. Возьмите VCL Delphi 7 и вы увидите что такое «не тормозит».
— WPF на железе 2005 года — летает
В базовом функционале возможно. Пробовал один заокругленный прямоугольник с анимированным внешним глоу — уже ощутил тормоза. Но в чистом WPF у меня опыта мало.
SL — тоже все летает, если руки правильно заточены
У нас до сих пор один проект на эксплуатации. В целом неплохо, но проскоки кадров наблюдаются. Плюс глюков там просто тьма. Пока реализовали нормальные окна не глючащие при изменении масштаба все волосы на себе повыдергивали.
— Это проблема всех проектов, где работает больше 1 человека
Мне не интерессно сколько там человек работает. Если в структурах нет ООП, то я не должен уметь перегружать GetHashCode, Equals и ToString, а если могу, то не только их.
— О каких коллекциях конкретно идет речь?
Скажите чем отличаются ArrayList, List и Collection и почему они так названы? Ну и помогите разгребсти следующую кашу: OrderedDictionary, StringDictionary, NameValueCollection, ListDictionary, SortedList, SortedDictionary, Dictionary, Hashtable…
— Скорость разработки или скорость выполнения конкретных методов?
Скорость выполнения конечно.
Есть реальный опыт, чем можете поделитсья?
— WinForms — летает
Жутко тормозит даже на современном железе, многие жалуются. Поставьте бекграунд на форме, гриду с парой десятком колонок, якоря и увидите. Возьмите VCL Delphi 7 и вы увидите что такое «не тормозит».
— WPF на железе 2005 года — летает
В базовом функционале возможно. Пробовал один заокругленный прямоугольник с анимированным внешним глоу — уже ощутил тормоза. Но в чистом WPF у меня опыта мало.
SL — тоже все летает, если руки правильно заточены
У нас до сих пор один проект на эксплуатации. В целом неплохо, но проскоки кадров наблюдаются. Плюс глюков там просто тьма. Пока реализовали нормальные окна не глючащие при изменении масштаба все волосы на себе повыдергивали.
— Это проблема всех проектов, где работает больше 1 человека
Мне не интерессно сколько там человек работает. Если в структурах нет ООП, то я не должен уметь перегружать GetHashCode, Equals и ToString, а если могу, то не только их.
— О каких коллекциях конкретно идет речь?
Скажите чем отличаются ArrayList, List и Collection и почему они так названы? Ну и помогите разгребсти следующую кашу: OrderedDictionary, StringDictionary, NameValueCollection, ListDictionary, SortedList, SortedDictionary, Dictionary, Hashtable…
— Скорость разработки или скорость выполнения конкретных методов?
Скорость выполнения конечно.
Выгода C#, Java и других подобных языков познается при разработке крупных бизнесс-приложений. Вы пытаетесь сравнивать два инструмента, которые предназначены для разных целей. Простая метафора: резец для резьбы по дереву и бензопила. Оба вроде как режут древесину, но цели перед ними стоят совершенно разные: резцом вы можете выточить произведение исскуства, но когда перед вами стоит задача срубить десяток деревьев, вы наверняка выберете более подходящий для этих целей инструмент — бензопилу.
C — резец по дереву в мире программирования, очень тонкий и элегантный инструмент. C# — современная высокоэффективная бензопила со встроенным GPS. Да, местами неуклюжая и возможно требующая дополнительных ресурсов, но очень эффективная для своих задач.
C — резец по дереву в мире программирования, очень тонкий и элегантный инструмент. C# — современная высокоэффективная бензопила со встроенным GPS. Да, местами неуклюжая и возможно требующая дополнительных ресурсов, но очень эффективная для своих задач.
Эх… Вот в области бизнес приложений никогда не работал… Но вот и спраживается же: а чего в них такого особенного, что бензопилой для них являются именно Java и C#?
Вот есть же действительно сложные приложения: Postfix, MPlayer, Abiword, ViM. Они оперируют в сложных режимах сложными данными… Но почему-то они успешно пишутся на Си и успешно при этом развиваются… Или вот исходники игрушек промышленных, иногда утекают, и можно посмотреть, тоже вполне сложные модели с сетевым взаимодействием, серверами и прочими рюшечками пишуться на довольно примитивном С++, даже без шаблонов и исключений, редко когда с наследованием.
Чем от них существенно отличаются крупные бизнесс-приложения? Было бы интересно узнать.
Вот есть же действительно сложные приложения: Postfix, MPlayer, Abiword, ViM. Они оперируют в сложных режимах сложными данными… Но почему-то они успешно пишутся на Си и успешно при этом развиваются… Или вот исходники игрушек промышленных, иногда утекают, и можно посмотреть, тоже вполне сложные модели с сетевым взаимодействием, серверами и прочими рюшечками пишуться на довольно примитивном С++, даже без шаблонов и исключений, редко когда с наследованием.
Чем от них существенно отличаются крупные бизнесс-приложения? Было бы интересно узнать.
Существенное отличие современных крупных бизнесс-приложений от Postfix, MPlayer, Abiword и ViM в том, что все четыре вышеупомянутых приложения начали создаватся еще в 90-х/начеле 2000-х годов, когда C# вообще не было, а Java была слишком тяжелой и неповоротливой для железа тех времен, да возможностей давала поменьше чем сейчас. Еще один существенный фактор — все эти проекты открытые и начинали разрабатыватся энтузиастами, которые, как правило, не особо задумываются над бюджетами, сроками и человеко-часами, с которыми обязательно нужно считатся в мире бизнеса.
В случае промышленных игр огромную роль имеет производительность. Цель большинства разработчиков современных игр — выжать максимум из железа пользователя, чтобы показать ему максимально привлекательную картинку. В ход идут самописные аллокаторы памяти, различные хаки, микрооптимизации и т.п. В этом случае они оправданы, так как дают игре конкурентное преимущество, которое выливается в дополнительный доход, который окупает расходы на все эти усилия. Впрочем довольно часто на С++ пишут только критические части движка, а вот все остальное уже на более высокоуровневом языке.
В случае с подавляющим большинством бизнесс-приложений основными требованиями являются:
а) надежность — утечки памяти или access violation в случае кривого обращения с указателем могут стоить заказчику миллионы долларов. Конечно, использование C# или Java не даст вам 100% гарантии от ошибок, но уменьшит их очень значительно.
б) качество кода — многие бизнесс-приложения живут десятилетиями и их поддерживают и дописывают целые поколения разработчиков. Поэтому код пишется по определенным стандартам, с использованием общепринятых компонентов и с пониманием того, что через 10 лет кому-то, кто сейчас возможно ходит в начальную школу, придется в этом коде разобратся.
в) общая цена вопроса — поставьте себя на место заказчика. К нему приходят два менеджера команд разработчиков: один обещает написать нужное вам приложение на С++ за год и оно будет работать на железе за 1000 у.е., а другой — за пол года на C#, но оно будет требовать дополнительную оперативку, а значит вам придется покупать железо за 1200 у.е. При этом месяц работы каждой комманды стоит 50 тысяч у.е. Кого вы выберете?
Код на С или С++ без сложных ООП конструкций очень хорошо и понятно выглядит по сравнению с кодом, написанном в ООП-стиле до тех пор, пока приложение не разрастается до определенного уровня. Когда обьем кода на С превышает 10000 строк, в нем становится трудно разбиратся. Когда его больше 100000 строк — разобратся в нем могут только настоящие гуру. Когда счет начинает идти на миллионы — в коде на С разобратся не сможет никто. В то же время, с правильно спроектированными приложениями обьемом в миллионы строк на C# вполне возможно работать, это я вам по собственному опыту говорю.
В случае промышленных игр огромную роль имеет производительность. Цель большинства разработчиков современных игр — выжать максимум из железа пользователя, чтобы показать ему максимально привлекательную картинку. В ход идут самописные аллокаторы памяти, различные хаки, микрооптимизации и т.п. В этом случае они оправданы, так как дают игре конкурентное преимущество, которое выливается в дополнительный доход, который окупает расходы на все эти усилия. Впрочем довольно часто на С++ пишут только критические части движка, а вот все остальное уже на более высокоуровневом языке.
В случае с подавляющим большинством бизнесс-приложений основными требованиями являются:
а) надежность — утечки памяти или access violation в случае кривого обращения с указателем могут стоить заказчику миллионы долларов. Конечно, использование C# или Java не даст вам 100% гарантии от ошибок, но уменьшит их очень значительно.
б) качество кода — многие бизнесс-приложения живут десятилетиями и их поддерживают и дописывают целые поколения разработчиков. Поэтому код пишется по определенным стандартам, с использованием общепринятых компонентов и с пониманием того, что через 10 лет кому-то, кто сейчас возможно ходит в начальную школу, придется в этом коде разобратся.
в) общая цена вопроса — поставьте себя на место заказчика. К нему приходят два менеджера команд разработчиков: один обещает написать нужное вам приложение на С++ за год и оно будет работать на железе за 1000 у.е., а другой — за пол года на C#, но оно будет требовать дополнительную оперативку, а значит вам придется покупать железо за 1200 у.е. При этом месяц работы каждой комманды стоит 50 тысяч у.е. Кого вы выберете?
Код на С или С++ без сложных ООП конструкций очень хорошо и понятно выглядит по сравнению с кодом, написанном в ООП-стиле до тех пор, пока приложение не разрастается до определенного уровня. Когда обьем кода на С превышает 10000 строк, в нем становится трудно разбиратся. Когда его больше 100000 строк — разобратся в нем могут только настоящие гуру. Когда счет начинает идти на миллионы — в коде на С разобратся не сможет никто. В то же время, с правильно спроектированными приложениями обьемом в миллионы строк на C# вполне возможно работать, это я вам по собственному опыту говорю.
Удивительно, но мне есть, что вам сказать: ) несмотря на то, что у меня нет опыта работы в сфере бизнес-приложений. Хотя, у меня есть опыт работы над программами, которые надо было сдавать регулярно и в срок. Сразу прошу, читая следующее, не думать о том, что я религиозный фанатик; я лишь хочу добраться до некой истины, которая, наверняка где-нибудь скрыта и в C#, и в Java. Поэтому, дьявольски адвокатствуя, буду пинать Ваши доводы.
1. MPlayer, например, начали разрабатывать в 2000 году, когда уже был весьма развит C++. И разработчики вполне могли бы использовать все его 'прелести'. Кроме того, я назвал эти программы, как примеры больших проектов, достаточно сложных, с большим числом участников, которые успешно развиваются на основе Си.
2. Насчёт игр вы преувеличиваете. Не так уж много там оптимизаций. Разработчики даже циклы уже не разворачивают, просто полагаясь на компилятор. Такты там вручную никто не считает, потому что опять же, главное в современных играх — это сложные модели, сложная математика. Какой-нибудь шейдер средней сложности можно так на ассемблере и не написать никогда, поэтому их пишут на высокоуровневых языках тоже, заботу об оптимизации в большинстве случаев скидывая на компилятор.
Гораздо важнее высокоуровневая оптимизация — выбор правильных структур данных, всё такое. Потому что современная игрушка управляет и согласовывает работу десятков сложных математических моделей. При чём пишут их не в одной конторе, а в 10 разных: одни мимкой занимаются, другие, не знаю, поведением ткани, например.
Можете посмотреть Source, который до сих пор по ed2k гуляет, и, уверен, Вы найдёте там 100-500 мест, где Вы бы код написали оптимальнее.
3. С заявлением о надёжности согласен, но не до конца. Про утечки памяти: вот буквально сегодня пришлось разбираться с кодом на C#, в котором dispose не вызывался во время. Вроде как сборка мусора, но какая-то не до конца… Аналогом же Access Violation в полный рост является выход за границу массива.
И, ведь что интересно, в том же UNIX, вполне себе можно Access Violation обработать без краха приложения. Можно отловить сигнал. А если некогда разбираться, можно даже изолировать потенциально опасные куски кода в отдельные процессы. Можно даже в эти процессы изолировать код с потенциальными утечками памяти, чтобы потом освобождать все ресурсы одним махом. Можно для этого использовать стандартные watchdog'и, которые будут отслеживать поведение процессов. Вообще, на этот счёт выработана куча техник программирования и отладки. Вопрос в том, почему про них никто не знает?
4. Про платформу согласен. Да, платформы в бизнесе долгоживущие. И вот моя теория заговора: очень выгодно предложить очень сложную в реализации платформу, со сложным компилятором, со сложным runtime, чтобы привязать клиента к себе. Mono, конечно, героический проект, но по качеству они .Net проигрывают существенно.
Но вот оправдана ли технически эта сложность? Зависшие в памяти объекты бывают? Бывают. Неотловленные исключения с выходами за границы или ещё с какими ситуациями проскакивают? Проскакивают и прерывают приложение. Бедлам в библиотеках присутствует? Присутствует… Всё это похоже на легенды о COBOL, хотя, конечно C# удобнее стократно.
5. Про разработчиков: остаётся только сравнить, а действительно ли сроки разработки так существенно рознятся для С++ и C#? А вообще, лично я, выбрал бы разработчиков на С++, и попросил бы их писать на Си. И вот почему: хорошо, я переплачу 600 000 у.е., но я получу (1) широко переносимый код — захочу, буду гонять его на Solaris с минимальным переписыванием, а захочу — на FreeBSD под Itanium'ом; (2) код, в работе которого нет никаких загадок, связанных со взаимодействием сложных систем типов; (3) код, который просто потом распилить на кучу библиотек, простым копи-пастом. И, кстати, я ещё и не уверен, что мне действительно придётся переплачивать.
Было бы, на самом деле, замечательно устроить какое-нибудь подобное соревнование: на чём быстрее можно написать сложную программу… Хм. Хотя, вот, возьмём для примера, какую-нибудь torrent-качалку. Их в природе существует великое множество, и пишут их на разных языка, и это логически, довольно сложные программы. Есть библиотека на C# — MonoTorrent, есть библиотека на Си — libtransmission. У первой объём исходников 2.1Mb, у второй — 1.5Mb… Функциональность при этом примерно одинаковая. По строкам, кстати, занятно: libtransmission на 8000 строк длиннее.
6. А какой объём кода, по-вашему, у ядра Linux? Однако ж, люди в нём разбираются, пишут модули, развивают весьма активно.
1. MPlayer, например, начали разрабатывать в 2000 году, когда уже был весьма развит C++. И разработчики вполне могли бы использовать все его 'прелести'. Кроме того, я назвал эти программы, как примеры больших проектов, достаточно сложных, с большим числом участников, которые успешно развиваются на основе Си.
2. Насчёт игр вы преувеличиваете. Не так уж много там оптимизаций. Разработчики даже циклы уже не разворачивают, просто полагаясь на компилятор. Такты там вручную никто не считает, потому что опять же, главное в современных играх — это сложные модели, сложная математика. Какой-нибудь шейдер средней сложности можно так на ассемблере и не написать никогда, поэтому их пишут на высокоуровневых языках тоже, заботу об оптимизации в большинстве случаев скидывая на компилятор.
Гораздо важнее высокоуровневая оптимизация — выбор правильных структур данных, всё такое. Потому что современная игрушка управляет и согласовывает работу десятков сложных математических моделей. При чём пишут их не в одной конторе, а в 10 разных: одни мимкой занимаются, другие, не знаю, поведением ткани, например.
Можете посмотреть Source, который до сих пор по ed2k гуляет, и, уверен, Вы найдёте там 100-500 мест, где Вы бы код написали оптимальнее.
3. С заявлением о надёжности согласен, но не до конца. Про утечки памяти: вот буквально сегодня пришлось разбираться с кодом на C#, в котором dispose не вызывался во время. Вроде как сборка мусора, но какая-то не до конца… Аналогом же Access Violation в полный рост является выход за границу массива.
И, ведь что интересно, в том же UNIX, вполне себе можно Access Violation обработать без краха приложения. Можно отловить сигнал. А если некогда разбираться, можно даже изолировать потенциально опасные куски кода в отдельные процессы. Можно даже в эти процессы изолировать код с потенциальными утечками памяти, чтобы потом освобождать все ресурсы одним махом. Можно для этого использовать стандартные watchdog'и, которые будут отслеживать поведение процессов. Вообще, на этот счёт выработана куча техник программирования и отладки. Вопрос в том, почему про них никто не знает?
4. Про платформу согласен. Да, платформы в бизнесе долгоживущие. И вот моя теория заговора: очень выгодно предложить очень сложную в реализации платформу, со сложным компилятором, со сложным runtime, чтобы привязать клиента к себе. Mono, конечно, героический проект, но по качеству они .Net проигрывают существенно.
Но вот оправдана ли технически эта сложность? Зависшие в памяти объекты бывают? Бывают. Неотловленные исключения с выходами за границы или ещё с какими ситуациями проскакивают? Проскакивают и прерывают приложение. Бедлам в библиотеках присутствует? Присутствует… Всё это похоже на легенды о COBOL, хотя, конечно C# удобнее стократно.
5. Про разработчиков: остаётся только сравнить, а действительно ли сроки разработки так существенно рознятся для С++ и C#? А вообще, лично я, выбрал бы разработчиков на С++, и попросил бы их писать на Си. И вот почему: хорошо, я переплачу 600 000 у.е., но я получу (1) широко переносимый код — захочу, буду гонять его на Solaris с минимальным переписыванием, а захочу — на FreeBSD под Itanium'ом; (2) код, в работе которого нет никаких загадок, связанных со взаимодействием сложных систем типов; (3) код, который просто потом распилить на кучу библиотек, простым копи-пастом. И, кстати, я ещё и не уверен, что мне действительно придётся переплачивать.
Было бы, на самом деле, замечательно устроить какое-нибудь подобное соревнование: на чём быстрее можно написать сложную программу… Хм. Хотя, вот, возьмём для примера, какую-нибудь torrent-качалку. Их в природе существует великое множество, и пишут их на разных языка, и это логически, довольно сложные программы. Есть библиотека на C# — MonoTorrent, есть библиотека на Си — libtransmission. У первой объём исходников 2.1Mb, у второй — 1.5Mb… Функциональность при этом примерно одинаковая. По строкам, кстати, занятно: libtransmission на 8000 строк длиннее.
6. А какой объём кода, по-вашему, у ядра Linux? Однако ж, люди в нём разбираются, пишут модули, развивают весьма активно.
Ну давайте по пунктам.
1. Я не имею представления, почему авторы MPlayer выбрали чистый С вместо С++. И вообще мне лично С нравится больше чем С++. Последний довольно уродский и перегруженный, я с этим согласен. Но, C# — это не С++, он намного стройнее, проще и продуманнее.
2. Я вообще к тому, почему там С++, а не C#, Java или какой-либо другой управляемый язык, например. Про согласование десятков моделей, потоков и сущностей в рамках игры я с вами полностью согласен. И мне страшно представить, насколько сложно это делать на чистом С без использования паттернов ООП. Кстати, «ООП» не обязательно означает десятиэтажные иерархии классов, во всем ведь можно соблюдать меру.
3. Дело не в присутствии или отсутствии определенных ошибок, а о вероятности их появления. Управляемые языки сильно понижают вероятность появления таких ошибок, и никто не говорил, что они претендуют на то, чтобы устранить их вообще. Код пишут люди, а они имеют свойство ошибатся. Язык может только понизить вероятность и сделать часть работы за разработчика.
Про выход за границу массива, извините, нет. Аналог выхода за границу массива в C# — это, сюрприз, выход за границу массива в С++. А access violation — это все таки обращение к обьекту, которого не существует, что бывает в управляемых языках очень редко. Исключение — null reference, но это немного не то и возникает такая ситуация обычно по глупости разработчика, когда обьект не был правильно проинициализирован.
Про то, что можно обработать, а что нельзя. Вообще, сам .Net вроде как написан на С++. А компилятор С++ в свою очередь, вполне возможно написать на С. То есть при определенном желании вы можете на С написать нечто, что даст вам все возможности C#. Вот только сколько времени и сил вы на это потратите? То есть выбирая более высокоуровневый язык вы просто избавляете себя от лишней работы, которую необходимо проделать на более низкоуровневом.
4. Мне тут нечего ответить, извините, я в теории заговора в программировании не верю. Я здесь деньги зарабатываю. На последний абзац могу ответить то же, что и в предыдущем пункте: никто и не говорил, что C# — идеален, и мозг включать при написании кода все равно надо. Самое главное его преимущество — это то, что можно сконцентрироватся на задаче, а не думать о том, какой поток должен освободить память, если обьект создан в одном потоке, передан во второй и при этом его использует третий.
5. Да, разнятся и очень сильно. Будет либо дольше, либо сильно дороже, за счет привлечение большего количества и более опытных разработчиков.
По поводу выбора, лично вы — программист и мыслите своими категориями. Заказчика не волнует на чем написан софт, если ему сказать, что на сервере должен стоять Windows Server 2008 R2 и только, то он его поставит. Ему совершенно все равно как типы взаимодействуют в системе (кстати, я в упор не понимаю, что вы имеете ввиду, когда пишете о загадках при взаимодействии — при правильной архитектуре приложения в нем нет никаких загадок). И ничего он распиливать не собирается. Ему надо чтобы работало, надежно, удобно и дешево.
Зачем соревнования? Бизнес уже давно выбрал Java и С#, потому что они дешевле и надежнее чем С++. Поверьте, этим ребятам плевать на религию, их интересуют только деньги, и когда они их вкладывают в софт на управляемых языках — за этим стоит обдуманное решение. Возвращаясь к вышеупомянутому Postfix, один из его конкурентов, MS Exchange исторически написан на С++. Сейчас его потихоньку, модуль за модулем переводят на C#. Конечно можно возразить, что C# — разработка MS, но нужно понимать, что один из самых популярних С++-компиляторов тоже разрабатывается этой компанией, а Exchange — стратегический продукт, который приносит миллиарды долларов каждый год, в разы больше, чем все средства разработки, в том числе C#.
6. Ядро Windows тоже написано на С. И обьемы там не маленькие. Просто для написания операционок или драйверов никто еще не придумал ничего лучше чем С. Но прикладной уровень — это другое дело.
1. Я не имею представления, почему авторы MPlayer выбрали чистый С вместо С++. И вообще мне лично С нравится больше чем С++. Последний довольно уродский и перегруженный, я с этим согласен. Но, C# — это не С++, он намного стройнее, проще и продуманнее.
2. Я вообще к тому, почему там С++, а не C#, Java или какой-либо другой управляемый язык, например. Про согласование десятков моделей, потоков и сущностей в рамках игры я с вами полностью согласен. И мне страшно представить, насколько сложно это делать на чистом С без использования паттернов ООП. Кстати, «ООП» не обязательно означает десятиэтажные иерархии классов, во всем ведь можно соблюдать меру.
3. Дело не в присутствии или отсутствии определенных ошибок, а о вероятности их появления. Управляемые языки сильно понижают вероятность появления таких ошибок, и никто не говорил, что они претендуют на то, чтобы устранить их вообще. Код пишут люди, а они имеют свойство ошибатся. Язык может только понизить вероятность и сделать часть работы за разработчика.
Про выход за границу массива, извините, нет. Аналог выхода за границу массива в C# — это, сюрприз, выход за границу массива в С++. А access violation — это все таки обращение к обьекту, которого не существует, что бывает в управляемых языках очень редко. Исключение — null reference, но это немного не то и возникает такая ситуация обычно по глупости разработчика, когда обьект не был правильно проинициализирован.
Про то, что можно обработать, а что нельзя. Вообще, сам .Net вроде как написан на С++. А компилятор С++ в свою очередь, вполне возможно написать на С. То есть при определенном желании вы можете на С написать нечто, что даст вам все возможности C#. Вот только сколько времени и сил вы на это потратите? То есть выбирая более высокоуровневый язык вы просто избавляете себя от лишней работы, которую необходимо проделать на более низкоуровневом.
4. Мне тут нечего ответить, извините, я в теории заговора в программировании не верю. Я здесь деньги зарабатываю. На последний абзац могу ответить то же, что и в предыдущем пункте: никто и не говорил, что C# — идеален, и мозг включать при написании кода все равно надо. Самое главное его преимущество — это то, что можно сконцентрироватся на задаче, а не думать о том, какой поток должен освободить память, если обьект создан в одном потоке, передан во второй и при этом его использует третий.
5. Да, разнятся и очень сильно. Будет либо дольше, либо сильно дороже, за счет привлечение большего количества и более опытных разработчиков.
По поводу выбора, лично вы — программист и мыслите своими категориями. Заказчика не волнует на чем написан софт, если ему сказать, что на сервере должен стоять Windows Server 2008 R2 и только, то он его поставит. Ему совершенно все равно как типы взаимодействуют в системе (кстати, я в упор не понимаю, что вы имеете ввиду, когда пишете о загадках при взаимодействии — при правильной архитектуре приложения в нем нет никаких загадок). И ничего он распиливать не собирается. Ему надо чтобы работало, надежно, удобно и дешево.
Зачем соревнования? Бизнес уже давно выбрал Java и С#, потому что они дешевле и надежнее чем С++. Поверьте, этим ребятам плевать на религию, их интересуют только деньги, и когда они их вкладывают в софт на управляемых языках — за этим стоит обдуманное решение. Возвращаясь к вышеупомянутому Postfix, один из его конкурентов, MS Exchange исторически написан на С++. Сейчас его потихоньку, модуль за модулем переводят на C#. Конечно можно возразить, что C# — разработка MS, но нужно понимать, что один из самых популярних С++-компиляторов тоже разрабатывается этой компанией, а Exchange — стратегический продукт, который приносит миллиарды долларов каждый год, в разы больше, чем все средства разработки, в том числе C#.
6. Ядро Windows тоже написано на С. И обьемы там не маленькие. Просто для написания операционок или драйверов никто еще не придумал ничего лучше чем С. Но прикладной уровень — это другое дело.
1. Ну, если просмотреть бегло списки рассылки MPlayer, то вывод складывается примерно такой: разработчики не особо понимают, как им поможет С++ в их работе. Выигрыша по скорости нет, выигрыша по сложности тоже, похоже нет (они смотрели на какие-то другие проигрыватели).
2. Объекты вполне можно создавать и на Си. При чём синтаксис даже проще, чем тот, что в C++ нужен для этого. Например, Postfix — он объектно-ориентированный, да и Linux тоже. Игры же пишут люди на Си вполне себе. Хотя, вот, вроде, в id Tech 4 Кармак переключился на Си++, но тут ещё надо посмотреть (вроде, исходники в этом году обещают показать), как он переключился. Потому что, вот в том же Source, С++ почти без наследования используется. Скорее уж как нечто, поддерживающее динамические модули.
5. Так я не соревнуюсь, пытаюсь понять, почему бизнес эти языки выбрал.
6. Linux я привёл, как проект с миллионом строк кода, написанный на Си, в котором люди успешно разбираются.
2. Объекты вполне можно создавать и на Си. При чём синтаксис даже проще, чем тот, что в C++ нужен для этого. Например, Postfix — он объектно-ориентированный, да и Linux тоже. Игры же пишут люди на Си вполне себе. Хотя, вот, вроде, в id Tech 4 Кармак переключился на Си++, но тут ещё надо посмотреть (вроде, исходники в этом году обещают показать), как он переключился. Потому что, вот в том же Source, С++ почти без наследования используется. Скорее уж как нечто, поддерживающее динамические модули.
5. Так я не соревнуюсь, пытаюсь понять, почему бизнес эти языки выбрал.
6. Linux я привёл, как проект с миллионом строк кода, написанный на Си, в котором люди успешно разбираются.
Извините, что встреваю. Мне кажется, что бизнес выбирает между Си (где средняя з/п, образно, $100) и php (где средняя з/п 60$). И выбор попадает на Java/C# (где средняя з/п 80$). Это условно весьма. Объективно выучиться на обычного программиста на php легче, чем на обычного сишника, поскольку в итоге всем надо знать http/html/db, но сишнику надо быть внимательным к памяти, к понятиям значение/указатель/ссылка и т.п. Т.е. усреднённый разработчик приложения получается дороже. Плюс к этому, чем выше компетенция, тем меньше человек количественно. А спрос на программистов у бизнеса больше, чем предложение…
И, возможно, даже не в «компетентности» дело, а в лаге — когда программист начнёт давать выхлоп. Из-за того, что «управляемые» платформы скрывают от программистов некоторые детали, которые обязаны знать «неуправляемые» программисты — лаг снижается. Хотя, мне так кажется, что действительно хороший программист на «управляемой» платформе должен по меньшей мере представлять, что его код творит с памятью, во что этот код трансформируется в рантайме (и платформа даёт ему возможность узнать эти детали после — гандикап своеобразный).
И, возможно, даже не в «компетентности» дело, а в лаге — когда программист начнёт давать выхлоп. Из-за того, что «управляемые» платформы скрывают от программистов некоторые детали, которые обязаны знать «неуправляемые» программисты — лаг снижается. Хотя, мне так кажется, что действительно хороший программист на «управляемой» платформе должен по меньшей мере представлять, что его код творит с памятью, во что этот код трансформируется в рантайме (и платформа даёт ему возможность узнать эти детали после — гандикап своеобразный).
А по-моему, сложность освоения Си преувеличена. Очень же простой язык с описанием, которое укладывается в тоненькую книжечку на 128 страниц. Лично у меня с Java было больше трудностей в освоении… Помнится, особую радость доставляла синхронизация и освобождение ресурсов (как в C# не знаю, не приходилось в production-условиях его использовать). На Си было проще.
Возможно, проблема с восприятием Си лежит в том, что людям пытаются (при чём, как бы, обоснованно и сознательно) навязать объектную модель мышления. А Си же раскрывает свой потенциал, когда обо всём думаешь, как о данных в памяти. А оно, ведь, всё действительно — данные в памяти. И такой подход открывает большие возможности.
А в Java (есть production-опыт у меня) очень много сил уходило на то, чтобы согласовывать работу нескольких объектов. Основное время тратилось не на собственно программирование алгоритмов анализа данных, а на всякие обёрточки, реализации интерфейсов и прочую ерунду. Да… И на синхронизацию с финализацией — тот ещё цирк был с освобождением некоторых ресурсов. И не уверен я, что это была работа на будущее.
Возможно, конечно, что мне просто такой участок работ достался, а в тех местах, где Java работает с базами данных, дела обстоят шикарно — не знаю.
Возможно, проблема с восприятием Си лежит в том, что людям пытаются (при чём, как бы, обоснованно и сознательно) навязать объектную модель мышления. А Си же раскрывает свой потенциал, когда обо всём думаешь, как о данных в памяти. А оно, ведь, всё действительно — данные в памяти. И такой подход открывает большие возможности.
А в Java (есть production-опыт у меня) очень много сил уходило на то, чтобы согласовывать работу нескольких объектов. Основное время тратилось не на собственно программирование алгоритмов анализа данных, а на всякие обёрточки, реализации интерфейсов и прочую ерунду. Да… И на синхронизацию с финализацией — тот ещё цирк был с освобождением некоторых ресурсов. И не уверен я, что это была работа на будущее.
Возможно, конечно, что мне просто такой участок работ достался, а в тех местах, где Java работает с базами данных, дела обстоят шикарно — не знаю.
Я могу судить о сложности освоения Си по своим одногруппникам/знакомым. Выборка не супер релевантная, но C# шёл несколько легче. С указателями вообще большая часть знакомых не могла работать. Уж не знаю почему. А утечки памяти — это вообще отдельная тема. Если лабораторная работа кушает 100 Мб — это уже о чём-то говорит :)
Вспомнил, когда-то работая в Terrasoft CRM, видел тонны кода для де/сериализации нативных объектов и потом когда уже перешел на C# увидел, что это занимает 3 строчки просто обалдел. Такая же история была со связыванием данных в памяти с визуальными компонентами.
Пример 1. Гибкость. Я пишу форму, которая умеет редактировать любой(!) объект, основываясь на типовой информация в рантайме (RTTI или рефлексия), например используя PropertyGrid. Можно сделать проверку обязательных полей и любую каcтомную валидацию основываясь на атрибутах. Атрибутами же упраляем доступностью полей для редактора, можно назначить свой редактор для поля и т.д. Редактируются вложенные объекты, включая коллекции. Кода немного, используются родные возможности. Вот например DevExpress FilterControl умеет на основе RTTI строить сложные фильтрационные выражения по свойствам любого объекта, которые потом можно использовать в where SQL. Пользу от этого просто сложно перееоценить. У нас одна форма используется для редактирования: конфигурационных файлов, настроек пользователя и системы (классы в БД), параметров отчетов.
Пример 2. Мощные фреймворки для бизнес задач. Я могу поднять трехзвенку (включая веб с рич клиентом) просто за отрицательное время практически без кода и поработав немного дизайнерами, используя: EntityFramework, WCF, RIAService, Silverlight. Классический веб можно через ASP Dynamic Data.
Пример 1. Гибкость. Я пишу форму, которая умеет редактировать любой(!) объект, основываясь на типовой информация в рантайме (RTTI или рефлексия), например используя PropertyGrid. Можно сделать проверку обязательных полей и любую каcтомную валидацию основываясь на атрибутах. Атрибутами же упраляем доступностью полей для редактора, можно назначить свой редактор для поля и т.д. Редактируются вложенные объекты, включая коллекции. Кода немного, используются родные возможности. Вот например DevExpress FilterControl умеет на основе RTTI строить сложные фильтрационные выражения по свойствам любого объекта, которые потом можно использовать в where SQL. Пользу от этого просто сложно перееоценить. У нас одна форма используется для редактирования: конфигурационных файлов, настроек пользователя и системы (классы в БД), параметров отчетов.
Пример 2. Мощные фреймворки для бизнес задач. Я могу поднять трехзвенку (включая веб с рич клиентом) просто за отрицательное время практически без кода и поработав немного дизайнерами, используя: EntityFramework, WCF, RIAService, Silverlight. Классический веб можно через ASP Dynamic Data.
А почему тогда не ещё более высокоуровневые языки? У Ruby, например, даже RPC прозрачный, а связь с SQL более, чем тесная. То, что вы написали, конечно, действительно очень важно, когда нужно быстро разрабатывать. Об этом я, пожалуй, задумаюсь: ) Спасибо.
Потому что покидая c# становится тоскливо — это раз.
Во вторых — c# это почти c++ по скорости выполнения кода, Ruby и ко — это как javaScript в плане производительности.
В третьих, в .Net есть такие вещи, как EF и Ado.Net — доступ к данным на любой вкус.
Во вторых — c# это почти c++ по скорости выполнения кода, Ruby и ко — это как javaScript в плане производительности.
В третьих, в .Net есть такие вещи, как EF и Ado.Net — доступ к данным на любой вкус.
Ну… Совсем даже не почти по скорости. Уступает, в среднем, в 2 раза. Но Ruby, да, сильно тормознее. Однако, код на Ruby том же, или Python, обычно, предназначен только для каких-то управляющих вещей: типа переконвертить HTTP-запрос в обращение к базе данных, запустить парсер полученных данных, и т.д. и т.п. Но, наверное да… По комбинации скорость/возможность доступа к данным C# с Java лучше всех… Надо бы это учесть, конечно, на будущее.
строка длиной 16 символов — это два числа по 64 бита или четыре числа по 32 бита
то есть все данные можно вообще хранить в одном массиве интов размером [X * (2 + 4)] для вашего случая
хеш-функцию от 4 интов написать тоже несложно.
то есть все данные можно вообще хранить в одном массиве интов размером [X * (2 + 4)] для вашего случая
хеш-функцию от 4 интов написать тоже несложно.
Получается 6 интов * 4 * 100 млн. = 2,4 Гб, такой блок памяти выделить практически невозможно. Плюс они должны быть отсортированы.
какие проблемы-то?
не выделяется одним куском — разбейте на два/четыре/N отдельных массивов
отсортируйте данные на этапе заполнения этих массивов (программа-то сперва эти 2.4 Гб данных откуда-то подсасывает так или иначе?)
и потом ищите по самому ключу.
никаких накладных расходов по памяти вообще нет.
не выделяется одним куском — разбейте на два/четыре/N отдельных массивов
отсортируйте данные на этапе заполнения этих массивов (программа-то сперва эти 2.4 Гб данных откуда-то подсасывает так или иначе?)
и потом ищите по самому ключу.
никаких накладных расходов по памяти вообще нет.
[sarcasm]Это слишком просто.
Статью-то тогда о чём писать.
[/sarcasm]Ок, согласен — равными блоками получится. Мы потратим еще немного на их организацию. По сути это то же что и сейчас, только блоки неравные и соответсвуют хешу. Нужно экспериментировать, но боюсь сортировка 100 млн. обойдется гораздо дороже подсчета хеша и поиска в цепочке.
Можно обойтись и без сортировки.
Да и затраты на загрузку 1M записей в Вашем варианте всяко будут велики. В «массивном» варианте скорость загрузки выше.
А реализация индекса может быть какой угодно.
Да и затраты на загрузку 1M записей в Вашем варианте всяко будут велики. В «массивном» варианте скорость загрузки выше.
А реализация индекса может быть какой угодно.
Какой например? Я так для себя понял, что можно сделать так:
— загружаем равными блоками (считаем одним массивом со сквозным индексом)
— сортируем
— умеем превращать ключ в индекс массива
— загружаем равными блоками (считаем одним массивом со сквозным индексом)
— сортируем
— умеем превращать ключ в индекс массива
1) не обязательно блоки делать равными. можно «с запасом» и заполнять не «до краев»
2) сортировать не обязательно после загрузки — можно и в процессе самой загрузки
3) да, после того как данные уже лежат в памяти можно уже думать — навернуть ли поверх этого еще какие-нибудь деревья и списки поиска либо просто по ключу искать данные, заранее зная что они отсортированы, а хэе-фенкция более-менее хорошо может сразу подсказать приблизительно индекс.
Детали уже зависят от задачи. Если памяти мало, а объем данных может в ближайшем будущем увеличиться — то одна стратегия. Если объем данных постоянен, а надо выжать скорость доступа — другая. Если напрягает первоначальная загрузка и сортировка — третья.
да, кстати. простите за банальный совет, если везде использовать 64-битные числа — то ключ — 2 числа и данные — одно число. только в самый последний момент разделить это на hi-lo. думаю, будет оптимальнее чем в 32-битном режиме. если сишарп это поддержит.
2) сортировать не обязательно после загрузки — можно и в процессе самой загрузки
3) да, после того как данные уже лежат в памяти можно уже думать — навернуть ли поверх этого еще какие-нибудь деревья и списки поиска либо просто по ключу искать данные, заранее зная что они отсортированы, а хэе-фенкция более-менее хорошо может сразу подсказать приблизительно индекс.
Детали уже зависят от задачи. Если памяти мало, а объем данных может в ближайшем будущем увеличиться — то одна стратегия. Если объем данных постоянен, а надо выжать скорость доступа — другая. Если напрягает первоначальная загрузка и сортировка — третья.
да, кстати. простите за банальный совет, если везде использовать 64-битные числа — то ключ — 2 числа и данные — одно число. только в самый последний момент разделить это на hi-lo. думаю, будет оптимальнее чем в 32-битном режиме. если сишарп это поддержит.
Если нужно добавление записей дибо изменение ключа — сортировка не вариант.
Я бы использовал для индекса что-нибудь максимально простое, ориентируясь на производительность.
Маппинг «N байт ключа»- «список указателей». Либо вариант со вложенным маппингом.
В зависимости от распределения ключа можно выбрать для маппинга либо List/Array либо Dictionary.
А вот древо я бы поостерёгся использовать, по крайней мере в универсальной реализации.
Кроме того, я бы не грузил все данные в память, а использовал бы memory mapped files.
Кстати, судя по тому, что ключ — строка, в реальном мире его скорее всего можно было бы ужать в более компактное битовое представление.
Я бы использовал для индекса что-нибудь максимально простое, ориентируясь на производительность.
Маппинг «N байт ключа»- «список указателей». Либо вариант со вложенным маппингом.
В зависимости от распределения ключа можно выбрать для маппинга либо List/Array либо Dictionary.
А вот древо я бы поостерёгся использовать, по крайней мере в универсальной реализации.
Кроме того, я бы не грузил все данные в память, а использовал бы memory mapped files.
Кстати, судя по тому, что ключ — строка, в реальном мире его скорее всего можно было бы ужать в более компактное битовое представление.
А можно поподробнее по поводу «Маппинг «N байт ключа»- «список указателей»»?
Спасибо за идею ужатия строки, действительно если использовать только латиницу, то мы умещаемся в половину байта и всю строку мы упаовываем в 8 байт! Надо уточнить у заказчика по поводу ограничения латиницей.
Спасибо за идею ужатия строки, действительно если использовать только латиницу, то мы умещаемся в половину байта и всю строку мы упаовываем в 8 байт! Надо уточнить у заказчика по поводу ограничения латиницей.
Если распределение более-менее ровное (например, ключ это MD5 хеш чего-либо), в качестве хеша для индекса/поиска есть смысл использовать, скажем, первые 3 байта ключа.
Создаём List|Array[0xFFFFFF], содержащий List со ссылками|смещениями элементов.
Вариант с вложенностью — основной List|Array[0xFFFFFF] содержит под-уровни (в зависимости от распределения ключа выбираем либо List либо Array), а они уже либо точное значение (для полного индекса ключа, если памяти не жалко), либо те же List со ссылками|смещениями элементов.
В сжатие данных эта техника называется DirectBytes.
И при всей своей простоте позволяет достичь весьма высокой скорости.
Единственный минус — требования по памяти в случае полного индекса, ну оно и понятно.
Кстати, очень советую посмотреть в сторону memory mapped files и уйти от хранения в памяти.
Тогда можно будет сделать действительно масштабируемую версию, а кроме того (если при изменении сохранять индекс в файл) ещё и с очень быстрой инициализацией.
Если со строками не повезёт и ключ окажется GUID'ным — советую инвертировать его побайтно (задом наперёд переписать то есть). Распределение будет со смещением в начало, а соответсвенно вырастет скорость поиска.
Не за что :)
Создаём List|Array[0xFFFFFF], содержащий List со ссылками|смещениями элементов.
Вариант с вложенностью — основной List|Array[0xFFFFFF] содержит под-уровни (в зависимости от распределения ключа выбираем либо List либо Array), а они уже либо точное значение (для полного индекса ключа, если памяти не жалко), либо те же List со ссылками|смещениями элементов.
В сжатие данных эта техника называется DirectBytes.
И при всей своей простоте позволяет достичь весьма высокой скорости.
Единственный минус — требования по памяти в случае полного индекса, ну оно и понятно.
Кстати, очень советую посмотреть в сторону memory mapped files и уйти от хранения в памяти.
Тогда можно будет сделать действительно масштабируемую версию, а кроме того (если при изменении сохранять индекс в файл) ещё и с очень быстрой инициализацией.
Если со строками не повезёт и ключ окажется GUID'ным — советую инвертировать его побайтно (задом наперёд переписать то есть). Распределение будет со смещением в начало, а соответсвенно вырастет скорость поиска.
Не за что :)
Расчитывать на распределение входных данных нельзя, для этого как раз счиатем хеш. Дальше, если по List|Array[0xFFFFFF] (затраты 67 Мб) мы имеем быстрый переход в область где начинаются коды с такими же первыми 3-мя байтами (возьмём этот случай, без вложенности), то теперь нам нужно найти такой же код обходя элементы. Т.е. либо это связанный список (400 Мб только на ссылках), либо просто список на каждый элемент масива (201 Мб), либо это один сплошной (разбитый на части), но отсортированный, а после проиндексированный сплошным проходом… По сути, в моей реализации, я могу заказать хешсегмент размером 0xFFFFFF и это будет подобная вещь, цепочка обхода будет в районе 100 / 16 = 6.
в чём проблема в 32битной системе выделить 2.4 гб, ещё можно понять. а в 64х?
или это проблема конкретно .NET'а?
или это проблема конкретно .NET'а?
Это проблема автора статьи
Попробуйте выделить такой объем одним блоком.
habrahabr.ru/blogs/net/114495/#comment_3693953
Лишь бы памяти хватило.
Да и про разбиение уже не раз сказали.
Лишь бы памяти хватило.
Да и про разбиение уже не раз сказали.
Автор правильно указал, что начинаются проблемы с выделением непрерывных блоков памяти из-за фрагментации. Блоки 500-700 МБ — компромиссный размер на подобных задачах (недавно разговаривал с парнем, работающим в HP — они софт для промышленных принтеров пишут, и сталкивались с подобными проблемами).
А нельзя было взять бесплатный SQL Express, который поддерживает базы размером до 4Гб и хранить данные там?
Может не стоит решать ресурсоёмкие задачи на C#? Всё-таки старичок C для этого подходит лучше. Особенно, учитывая тот факт, что из C# легко и просто дергать dll-ки написанные на C.
А то вначале создаем себе трудности, а потом героически их решаем.
А то вначале создаем себе трудности, а потом героически их решаем.
Да если б можно было. Проект большой и весь на С#. Решили не извращаться, а использовать то, что есть. Хотя по ходу работ мысли всякие возникали.
Ну так написать dll на C, которая реализует весь нужный функционал, дергать её из программы на C#. Будет всяко проще и быстрее.
Хм, или, как вариант, хранить всё в memcached :)
Хм, или, как вариант, хранить всё в memcached :)
Возникает вопрос: как это все поддерживать, отлаживать и т.д. Тут много нюансов, например сборка AnyCPU будет работать и на х32 и на х64 в родном режиме, а для native кода прийдется делать уже две сборки.
Я не уверен, что готовое решение будет очень оптимальным, оно скорее всего универсально и в подобной задаче может проиграть. Я не использовал memcached, но мне просто интересно, сколько она займет памяти на таких объемах.
Я не уверен, что готовое решение будет очень оптимальным, оно скорее всего универсально и в подобной задаче может проиграть. Я не использовал memcached, но мне просто интересно, сколько она займет памяти на таких объемах.
Ну пожалуйста, пощадите пользователей Хабра. Особенно разработчиков. Воспользуйтесь средствами подсветки кода! :)
Дико извиняюсь — я новичок тут у вас. Не осилил предмет. В помощи указано юзать тег source, но он не работает. В редакторе code, но без подсветки. Подскажите как правильно?
Работает. Нужно указать в аттрибуте язык — в вашем случае «cs»
www.bankinform.ru/habraeditor/ — это удобно
может конечно есть и другие, но я этим пользуюсь
может конечно есть и другие, но я этим пользуюсь
Может я чего и не понимаю, но помоему, лучшее решение описанной задачи простой массив + индекс.
В зависимости от требований по скорости/памяти/вкусу, сортируем/разбиваем на несколько массивов/солим-перчим.
В зависимости от требований по скорости/памяти/вкусу, сортируем/разбиваем на несколько массивов/солим-перчим.
100 миллионов записей * 4 байта на ссылку (минимум) получается 400 мб. Я не думаю что система даст выделить непрерывный участок памяти в 400 мб.
var arr = new long[1000*1000*100*16];
Console.WriteLine("Вот ведь");
У меня предсказуемый
Unhandled Exception: OutOfMemoryException.
Unhandled Exception: OutOfMemoryException.
unsafe fixed int tmp[1024*1024*1024];
~ $ mcs test.cs -unsafe
test.cs(5,20): error CS1664: Fixed size buffer `pub.tmp' of length `1073741824' and type `int' exceeded 2^31 limit
Compilation failed: 1 error(s), 0 warnings
~ $ mono -V
Mono JIT compiler version 2.8.2 (tarball Wed Feb 16 21:21:12 MSK 2011)
Copyright © 2002-2010 Novell, Inc and Contributors. www.mono-project.com
TLS: __thread
SIGSEGV: altstack
Notifications: epoll
Architecture: amd64
Disabled: none
Misc: debugger softdebug
LLVM: supported, not enabled.
GC: Included Boehm (with typed GC and Parallel Mark)
~ $ mcs test.cs -unsafe
test.cs(5,20): error CS1664: Fixed size buffer `pub.tmp' of length `1073741824' and type `int' exceeded 2^31 limit
Compilation failed: 1 error(s), 0 warnings
~ $ mono -V
Mono JIT compiler version 2.8.2 (tarball Wed Feb 16 21:21:12 MSK 2011)
Copyright © 2002-2010 Novell, Inc and Contributors. www.mono-project.com
TLS: __thread
SIGSEGV: altstack
Notifications: epoll
Architecture: amd64
Disabled: none
Misc: debugger softdebug
LLVM: supported, not enabled.
GC: Included Boehm (with typed GC and Parallel Mark)
и в то же время в си я спокойно выделяю и использую все свои 8 гб.
что показывает, что каждую задачу нужно решать тем инструментом, который лучше для этого подходит. и что автор статьи вначале поставил себе целый огород граблей, а потом мастерски их обошёл.
что показывает, что каждую задачу нужно решать тем инструментом, который лучше для этого подходит. и что автор статьи вначале поставил себе целый огород граблей, а потом мастерски их обошёл.
Одним malloc'ом все 8gb?
да. более того, на боевом сервере у меня
# ps auwx | grep xxx
root 13422 4.5 57.4 33334444 28413796 pts/8 S+ Feb24 73:51 ./xxx
и большая часть памяти выделилась одним куском в 28 гигабайт.
количество адресуемой памяти равно у нас 17179869184 гигабайт. в чём проблема найти там мизерный непрерывный кусок?
# ps auwx | grep xxx
root 13422 4.5 57.4 33334444 28413796 pts/8 S+ Feb24 73:51 ./xxx
и большая часть памяти выделилась одним куском в 28 гигабайт.
количество адресуемой памяти равно у нас 17179869184 гигабайт. в чём проблема найти там мизерный непрерывный кусок?
физически память, конечно, будет «не подряд» и выделится не сразу, а только при первом использовании (и да, windows тоже так умеет), но благодаря Таблице Страниц произойдёт трансляция адресов и память можно будет адресовать последовательно, как будто это на самом деле один кусок физической памяти, хотя на самом деле это стопицот кусков из которых половина ушла в своп.
А ну когда 17 гб стоит… у меня то 3 гб и 111 процессов болтается.
давайте ещё раз, на пальцах, чтобы всё было понятно.
попроще:
у нас есть некаяпамять и есть адресуемая память. адресовать мы можем 17179869184 гб. мы делаем malloc, получаем адрес. теперь в таблице страниц записано, что этому диапазону адресов соответствует блок некойпамяти.
если у вас физически есть свободная память, то вы почти всегда можете выделить её одним куском благодаря новейшим технологиям работы со страницами и виртуальной памятью (доступным с 93го года)
попроще:
у нас есть некаяпамять и есть адресуемая память. адресовать мы можем 17179869184 гб. мы делаем malloc, получаем адрес. теперь в таблице страниц записано, что этому диапазону адресов соответствует блок некойпамяти.
если у вас физически есть свободная память, то вы почти всегда можете выделить её одним куском благодаря новейшим технологиям работы со страницами и виртуальной памятью (доступным с 93го года)
ещё раз. количество адресуемой памяти = 17179869184 гигабайт. 17 МИЛЛИАРДОВ ГИГАБАЙТ. 17 ТЫСЯЧ ПЕТАБАЙТ. ЭТО НАВЕРНОЕ ВСЯ ПАМЯТЬ ВСЕХ КОМПЬЮТЕРОВ ЦЕЛОГО ДАТАЦЕНТРА ГУГЛА.
и под ваши жалкие 2.4 гигабайта будут выделяться адреса именно из этой огромной массы доступных адресов.
и под ваши жалкие 2.4 гигабайта будут выделяться адреса именно из этой огромной массы доступных адресов.
Хм, при таком объеме данных, можно сделать предположение, что вполне реально отделаться маленьким рабочим набором процесса. Сомневаюсь, что все 100М записей постоянно дергаются в процессе работы приложения. Т.е. скорее всего выгоднее в памяти держать только небольшой набор данных, обращение к которым происходит чаще всего. Я бы сделал DLL на C++, в которой бы использовал отображаемый в память файл, особым образом отформатированный, отсортированный и сгруппированный по хеш-кодам записей. Записи фиксированного размера, по этому всё просто. Поиск сделал бы бинарным прямо по отображению файла, а в .NET результат передавал бы маршалингом. Выделение памяти таким образом ложиться на диспетчер памяти Windows. Падение производительности — только при ошибках страниц. + повышение быстродействия за счет отсутствия неявных проверок выходов индексов за гарницы массива и других накладных расходов .NET.
В общем-то все вменяемые реализации СУБД работают примерно по похожему принципу — при помощи индексных файлов. К слову, можно было бы попробовать использовать портативную файловую СУБД для этих целей. Типа Jet RED (Access) или Jet BLUE (ESE). Ну или что-нибудь опен-сорсное.
В общем-то все вменяемые реализации СУБД работают примерно по похожему принципу — при помощи индексных файлов. К слову, можно было бы попробовать использовать портативную файловую СУБД для этих целей. Типа Jet RED (Access) или Jet BLUE (ESE). Ну или что-нибудь опен-сорсное.
Подозреваю, что JET тут не справится:) Они вон с Оракла в память данные сливают.
Оракл решал задачу сравнения двух таблиц (100 млн. vs 50 млн.) на сортированных данных — несколько часов, на несортированных — не дожидались. Выборка шла по ключам. В памяти это происходит за 15 минут.
А не пробовали использовать HashSet? В плане поиска, из стандартных коллекций, самая быстрая.
И у Вас получилось без лишних ухищрений создать объект (в Вашем случае — массив структур) объемом более 2Г?
Вопрос не случаен: .NET не позволяет этого делать.
Пруфлинк: «Как и в случае с 32-разрядными операционными системами Windows размер объекта, создаваемого при выполнении 64-разрядного управляемого приложения в 64-разрядной операционной системе Windows, ограничен 2 ГБ.»
Вопрос не случаен: .NET не позволяет этого делать.
Пруфлинк: «Как и в случае с 32-разрядными операционными системами Windows размер объекта, создаваемого при выполнении 64-разрядного управляемого приложения в 64-разрядной операционной системе Windows, ограничен 2 ГБ.»
Нет, до этого не дошло — уперлись в фрагментацию уже на 500 Мб. То, что есть ограничение блока на х64 не знал — спасибо.
Хм… у меня получалось создавать DataTable на 3Гб
Это возможно, поскольку в классе DataTable лежат лишь ссылки на данные, а не сами данные. Таким образом, размер объекта типа DataTable есть величина порядка sizeof(IntPtr) * Rows.Count + размеры остальных полей класса.
Будь классы DataRowCollection и DataRow структурами (что было бы, имхо, глупо), ограничение не осталось бы незамеченным.
Будь классы DataRowCollection и DataRow структурами (что было бы, имхо, глупо), ограничение не осталось бы незамеченным.
Автор изобрел memcached под .net… Хоть бы погуглил 5 минут, прежде чем тратить столько времени впустую.
В один прекрасный день записи все равно не влезут в память 1го сервера и что тогда?
В один прекрасный день записи все равно не влезут в память 1го сервера и что тогда?
Да я из гугла не вылезал. Нам нужна была своя реализация, которую можно поддерживать. Хотя очень интересно, как поведет себя готовое универсальное решение типа memcached на данных объемах. На х64 нет предела в 2 Гб и память очень весело выделяется даже после окончания физичечкой. На машине, указанной в примерах с 4 Гб я умудрялся выделять около 8 Гб. Всё тормозило, но работало. Так вот вам и ответ- всё будет тормозить. Но это не проблема, у нас свои сервера с экслюзивным доступом, так что 8 Гб физики нам должно хватить на долго.
Может у кого то есть опыт или ссылки на чужой опыт, относительно расположения большого кол-ва строк в памяти .NET приложения > 64k, реальные эксперименты показывают что реализация в лоб постепенно засоряет LOH.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Обработка больших объемов данных в памяти на C#