И там прямым текстом написано что в C++ есть требования к итераторам, которые не получится эффективно реализовать для b-tree. Да уж действительно серебрянная пуля…
Опа, а как же ваш «любимый» кеш? Бинарный поиск с O(logN) разве не эквивалентен бинарному дереву?
1. Я уже писал про TLB, который вы категорически игнорируете. 2. С деревьями не только поиск, вставку и удаление производят, по ним еще иногда и итерируются.
Хотя я вроде уже упоминал, что есть разные нагрузки, и утверждать, что одна структура лучше другой независимо от нагрзуки (как вы сделали и на что я вам уже указывал) странно.
Элементов в узле то больше. Чуть выше вы же говорили про бинарный поиск.
Да говорил и?
Почитайте любую книгу по теории структур данных и вы узнаете что любое дерево, в том числе и B-Tree можно представить в виде эквивалентного двоичного дерева.
И это гарантирует функциональную эквивалентность, но не одинаковую эффективность.
Такое дерево всегда будет иметь больше узлов, больше сравнений и менее сбалансированное (не обязательно буквально, ваш бинарный поиск это просто кусок этого бинарного дерева).
Бинарное дерево полученное из b-tree может быть, но вот b-tree это всегда идеально сбалансированное дерево поиска и с учетом бинарного поиска и без него (может вам стоит самому обратиться к книгам по алгоритмам?).
То, что на практике кеш ускоряет константную составляющую и B-tree во многих случаях выходит вперед не делает его универсальным.
И я ведь нигде не говорил про универсальность, более того прямым текстом указал вам, что как минимум существует проблема с итераторами. Но вы опять же это проигнорировали или просто не поняли (к вопросу про подростковую категаричность и нежелание слушать).
Давайте вы не будете за других решать что им обсуждать, а что нет.
Я ничего за других не решаю, а вам бы стоило перечитать свои же комментарии.
Вы педалируете идею что B-tree, чуть ли не, серебряная пуля и пора уже заменить все деревья на B-Tree.
Да ну? Покажите пожалуйста, где я такое утверждал?
в b-tree вам придется линейно пробегаться и вызывать большое число компараторов
А про бинарный поиск вы не слышали?
В двоичном дереве за одно сравнение вы сразу отсекаете половину элементов.
А в B-tree нет?
Выигрыш от кеша и локальности вы получите только при быстрых компараторах, если это возможно и POD-like элементах, на что в общем случае полагаться невозможно.
Вы пишете ерунду, из того, что на кеш и TLB локальность в общем случае нельзя полагаться никак не следует, что нужно их всегда игнорировать. И перед тем как делать такие сильные утверждения возьмите и потестируйте разные алгоритмы.
Вы не утверждали? А я вот читаю ваши комментарии и вижу обратное.
Нет мы обсуждали не стандартные контейнеры, а то что вы смешали кучу всего в кучу (при этом обвинив в этом кого-то другого), затем мы обсуждали ваше утверждение о том, что бинарные деревня поиска при работе в памяти быстрее чем b-tree (сильное утверждение без всяких оговорок, но, если и может быть), а затем мы обсуждали создателей STL и то какие они не дураки...
Вы не видите проблемы, а я вижу. Для b-tree можно реализовать итераторы, но если соблюдать все требования итераторов std::map, толку от такой реализации будет не много.
И да, то что создатели C++ не определили семантику std::map и его итераторов так, чтобы её можно было эффективно реализовать используя b-tree не делает их идиотами, но это и не делает b-tree медленнее бинарного дерева поиска и не делает ваши гадания фактами.
А может быть разработчикам STL нужно было соблюдать семантику итераторов описанную в стандарте и поэтому они решили использовать бинарное дерево поиска с которым проще этого добиться, а скорость и затраты памяти тут не причём? Может вы не будете выставлять свои гадания как подтвержденные факты?
Я вам тонко намекают, что вы зря критикует человека за то что он что-то там смешал, во первых потому что он ничего не смешивали, а как вы выразились "не стал уходить в дебри", а во вторых потому что вы сами много чего намешали в кучу.
И кстати придумать бинарное дерево поиска в котором базовые операции работают за квадрат, а не за линию, это нужно немного постараться.
1. вы мешаете в кучу амортизированные оценки и средние оценки, а это не одно и тоже;
2. двоичных деревьев поиска есть много разных и не все из них дают «амортизированный доступ» за O(log N), но вы их почему-то смешли в одну кучую;
3. ну и map — это стандартный контейнер C++, от него требуются определенные гарантии, но использование двоичного дерева поиска в качестве реализации не является одной из этих гарантий.
1. прежде всего, не значит всегда, b-tree очень успешно используется и для работы в оперативной памяти;
2. реализация в статье не работает с внешней памятью и вообще никаким образом не упоминает внешнюю память;
3. реализация в статье даже если бы работала с внешней памятью была бы не сильно эффективнее обычного бинарного дерева, потому что t = 2.
Зависит от архитектуры, ОС, отображения памяти и много чего другого. Но строго говоря с точки зрения стандарта, то это undefined behavior.
Но вот чего там не происходит, так это если компилятор не попросить, то он не будет вставлять в код проверки и если эти проверки не проходят вызывать какие-то функции, которые никто не определял. Как это по вашему мнению происходит в D.
И? То что это реализуемо как-то гарантирует мне стабильность рантайма? И что создатели компилятора не сломают его в очередном релизе? Это как-то меняет то обстоятельство, что статья ни слова об всем этом не говорит и с чего собственно обсуждение и началось?
В C нет исключений, так что не также как в C. В C если вы не вызовете abort явно, то компилятор его за вас вызывать не будет только потому, что вы решили работать с массивами, что полезно, если никакой реализации abort у вас нет.
Мой поинт был в том, что если разговор зашел о системном программировании, то есть гораздо более актуальные вещи для обсуждения чем синтаксис похожий на C. И выбор языка C в этой области вовсе не продиктован его синтаксисом и не синтаксис оставнавливает от перехода на другие языки. Что вы хотите сказать своими комментариями?
Если массивы хранятся так же как в C, то откуда берется размер массива?
Исключения могут требовать поддержки рантайма и полезно указать в чем она заключается, а не про синтаксис близкий к C рассказывать. И просто конвенция вызова «как в C» мало что дает.
Элементарно, если исключение не поймать, то программа должна по идее завершиться, но как завершать программу зависит от ОС. А что если у вас нет ОС?
Для некоторых портирование рантайма может оказаться сравнимо с написанием ядра ОС (менеджер памяти, процессов, реализация атомиков, api для файлов, сокетов и т. д. и т. п.).
Это очевидно зависит от того, как рантайм определен и от того кто его реализует. Если вы для JS VM определите рантайм из пары функций (например, аллоцировать память и освободить память), то его портирование не должно составить проблем. Отсюда и появился мой вопрос про рантайм.
Поэтому я склоняюсь к определению системного языка, как такого, на котором может быть реализовано, например, ядро ОС.
Я уверен, что на JS и Go можно реализовать ядро ОС. Ваше определение не добавляет ясности, отчасти потому что оно не определяет, что может называться ядром ОС, а что нет. Даже приведенный вами список компонентов ядра вызывает вопросы: известны примеры ядер ОС, которые прекрасно жили/живут без потоков и/или без процессов и/или файловых систем и/или сетевого стека в ядре.
extern вероятно задает конвенцию вызова, а речь не только о ней, а о поддержке рантайма. Например, в статье упоминается лучшая чем у C memory_safety, я полагаю, что это включает среди прочего проверку границ массивов. Что D делает, когда проверка не проходит? Какие функции нужно ему подложить, чтобы это все собралось? Как D представляет массивы в памяти, чтобы можно было настроить передачу данных между D и каким-нибудь firmware?
Чем больше фич язык включает тем больше таких вопросов возникает. В этом смысле сравнительно небогатый на фичи C просто не создавал таких проблем, и поэтому использовать его было довольно просто.
Так никто и не заставляет компилятор генерировать simd инструкции, если не указаны -march/-mtune и подобные вещи. Если dmd целится в системное программирование и ведёт себя не так — то это странно.
Я не знаю, как себя ведет D, то что я знаю это то, что статья начинается с упоминания системного программирования (и про какое-то мифическое отсутствие выбора), а потом говорит про синтаксис и фичи ни слова не сказав про ABI и рантайм нужный для поддержки этих фич, я молчу об их стабильности.
Вспомнить тот же x86_64, до нормальной работы нужно переключиться в защищенный режим, а потом и в long mode.
Если вам хватает Real Mode, то в защищенный режим переключать не надо (но тут у вас могут появиться проблемы при использовании, например, gcc), если вам хватает защищенного режима, то в long mode переключаться необходимости нет. Если компилятор поддерживает нужный вам режим, то он вполне пригоден, даже если он не поддерживает все на свете.
Меня какое-то время назад пытались убедить, что go и js — языки программирования системного уровня.
В зависимости от того, что они подразумевали под системным программированием оба языка могут являться таковыми. Мне не известно про какое-то оффициальное стандартизованное законно зафиксированное понятие системного языка программирования. Даже если в контексте данной статьи ограничиться расплывчатым смыслом «близости к железу», то оба языка можно с определенной долей усилий сделать системными создав минимальный рантайм.
SIMD инструкции могут требовать инициализации соответсвующих расширений процессора. Если вы опираетесь на ОС, то она возможно сделает это за вас (если умеет), а если вы с голым железом работаете, то придется это делать как часть инициализации.
Если компилятор для core фичи генерирует код использующий SIMD (прямо или через intrinsic-и), то это проблема, если это вынесено в библиотеку, использование которой опционально, то проблемы нет.
Под рантаймом имеются ввиду библиотеки, которые линкуются с вашей программой (и прочие вспомогательные средства), чтобы помогать компиялтору реализовывать фичи языка (такие как TLS или например код, который вызывает main с нужными argc и argv, или код которые вызывает конструкторы и деструкторы глобальных объектов и тд и тп), для которых компилятор не может просто сгенерировать код.
Если для распространненых сочетаний архитектура/ОС вы получаете рантайм вместе с компилятором, то для менее распространенных комбинаций это не так. Никто не помешает вам реализовать эти библиотеки, но если ABI не стабилен, то никто не помешает создателям компилятора сломать ваши библиотеки и весь ваш проект вместе с ним.
С чего бы это? Что gcc для таких вещей вдруг не требует поддержки рантайма? Или магическим образом умеет TLS на всех платформах, для которых он может генерировать код?
Мне немного непонятно, в статье упоминается про системное программирование, но, например, нет ни слова про рантайм. Всякие SIMD и TLS требуют какой-то поддержки, как это запускать на голом железе? Какие функции нужно подложить компилятору, чтобы это взлетело? Особенно, если железо отличается от чего-то очень широко распротранненого? Я не думаю, что причина, по которой некоторые системные программисты не редко работают с C, заключается в его синтаксисе.
1. Я уже писал про TLB, который вы категорически игнорируете. 2. С деревьями не только поиск, вставку и удаление производят, по ним еще иногда и итерируются.
Хотя я вроде уже упоминал, что есть разные нагрузки, и утверждать, что одна структура лучше другой независимо от нагрзуки (как вы сделали и на что я вам уже указывал) странно.
Да говорил и?
И это гарантирует функциональную эквивалентность, но не одинаковую эффективность.
Бинарное дерево полученное из b-tree может быть, но вот b-tree это всегда идеально сбалансированное дерево поиска и с учетом бинарного поиска и без него (может вам стоит самому обратиться к книгам по алгоритмам?).
И я ведь нигде не говорил про универсальность, более того прямым текстом указал вам, что как минимум существует проблема с итераторами. Но вы опять же это проигнорировали или просто не поняли (к вопросу про подростковую категаричность и нежелание слушать).
Да ну? Покажите пожалуйста, где я такое утверждал?
А про бинарный поиск вы не слышали?
А в B-tree нет?
Вы пишете ерунду, из того, что на кеш и TLB локальность в общем случае нельзя полагаться никак не следует, что нужно их всегда игнорировать. И перед тем как делать такие сильные утверждения возьмите и потестируйте разные алгоритмы.
Вы не утверждали? А я вот читаю ваши комментарии и вижу обратное.
Нет мы обсуждали не стандартные контейнеры, а то что вы смешали кучу всего в кучу (при этом обвинив в этом кого-то другого), затем мы обсуждали ваше утверждение о том, что бинарные деревня поиска при работе в памяти быстрее чем b-tree (сильное утверждение без всяких оговорок, но, если и может быть), а затем мы обсуждали создателей STL и то какие они не дураки...
Вы не видите проблемы, а я вижу. Для b-tree можно реализовать итераторы, но если соблюдать все требования итераторов std::map, толку от такой реализации будет не много.
И да, то что создатели C++ не определили семантику std::map и его итераторов так, чтобы её можно было эффективно реализовать используя b-tree не делает их идиотами, но это и не делает b-tree медленнее бинарного дерева поиска и не делает ваши гадания фактами.
А может быть разработчикам STL нужно было соблюдать семантику итераторов описанную в стандарте и поэтому они решили использовать бинарное дерево поиска с которым проще этого добиться, а скорость и затраты памяти тут не причём? Может вы не будете выставлять свои гадания как подтвержденные факты?
Вот просто так берет и уступает? Безотносительно нагрузки? А как насчёт кеш локальности и TLB локальности?
Я вам тонко намекают, что вы зря критикует человека за то что он что-то там смешал, во первых потому что он ничего не смешивали, а как вы выразились "не стал уходить в дебри", а во вторых потому что вы сами много чего намешали в кучу.
И кстати придумать бинарное дерево поиска в котором базовые операции работают за квадрат, а не за линию, это нужно немного постараться.
2. двоичных деревьев поиска есть много разных и не все из них дают «амортизированный доступ» за O(log N), но вы их почему-то смешли в одну кучую;
3. ну и map — это стандартный контейнер C++, от него требуются определенные гарантии, но использование двоичного дерева поиска в качестве реализации не является одной из этих гарантий.
2. реализация в статье не работает с внешней памятью и вообще никаким образом не упоминает внешнюю память;
3. реализация в статье даже если бы работала с внешней памятью была бы не сильно эффективнее обычного бинарного дерева, потому что t = 2.
Но вот чего там не происходит, так это если компилятор не попросить, то он не будет вставлять в код проверки и если эти проверки не проходят вызывать какие-то функции, которые никто не определял. Как это по вашему мнению происходит в D.
В C нет исключений, так что не также как в C. В C если вы не вызовете abort явно, то компилятор его за вас вызывать не будет только потому, что вы решили работать с массивами, что полезно, если никакой реализации abort у вас нет.
Мой поинт был в том, что если разговор зашел о системном программировании, то есть гораздо более актуальные вещи для обсуждения чем синтаксис похожий на C. И выбор языка C в этой области вовсе не продиктован его синтаксисом и не синтаксис оставнавливает от перехода на другие языки. Что вы хотите сказать своими комментариями?
Исключения могут требовать поддержки рантайма и полезно указать в чем она заключается, а не про синтаксис близкий к C рассказывать. И просто конвенция вызова «как в C» мало что дает.
Элементарно, если исключение не поймать, то программа должна по идее завершиться, но как завершать программу зависит от ОС. А что если у вас нет ОС?
Я уверен, что на JS и Go можно реализовать ядро ОС. Ваше определение не добавляет ясности, отчасти потому что оно не определяет, что может называться ядром ОС, а что нет. Даже приведенный вами список компонентов ядра вызывает вопросы: известны примеры ядер ОС, которые прекрасно жили/живут без потоков и/или без процессов и/или файловых систем и/или сетевого стека в ядре.
Чем больше фич язык включает тем больше таких вопросов возникает. В этом смысле сравнительно небогатый на фичи C просто не создавал таких проблем, и поэтому использовать его было довольно просто.
Если вам хватает Real Mode, то в защищенный режим переключать не надо (но тут у вас могут появиться проблемы при использовании, например, gcc), если вам хватает защищенного режима, то в long mode переключаться необходимости нет. Если компилятор поддерживает нужный вам режим, то он вполне пригоден, даже если он не поддерживает все на свете.
В зависимости от того, что они подразумевали под системным программированием оба языка могут являться таковыми. Мне не известно про какое-то оффициальное стандартизованное законно зафиксированное понятие системного языка программирования. Даже если в контексте данной статьи ограничиться расплывчатым смыслом «близости к железу», то оба языка можно с определенной долей усилий сделать системными создав минимальный рантайм.
Если компилятор для core фичи генерирует код использующий SIMD (прямо или через intrinsic-и), то это проблема, если это вынесено в библиотеку, использование которой опционально, то проблемы нет.
Если для распространненых сочетаний архитектура/ОС вы получаете рантайм вместе с компилятором, то для менее распространенных комбинаций это не так. Никто не помешает вам реализовать эти библиотеки, но если ABI не стабилен, то никто не помешает создателям компилятора сломать ваши библиотеки и весь ваш проект вместе с ним.