Каковы предостережения от реализации фундаментальных типов (таких как int) как классов?

27

При проектировании и implenting объектно-ориентированный язык программирования, в какой - то момент один должен сделать выбор о реализации основных типов (как int, float, doubleили их эквиваленты) , как классы или что - то другое. Очевидно, что языки в семействе C имеют тенденцию не определять их как классы (Java имеет специальные примитивные типы, C # реализует их как неизменяемые структуры и т. Д.).

Я могу думать об очень важном преимуществе, когда фундаментальные типы реализуются как классы (в системе типов с унифицированной иерархией): эти типы могут быть собственными подтипами Лискова корневого типа. Таким образом, мы избегаем усложнения языка боксом / распаковкой (явной или неявной), типов-оболочек, специальных правил отклонения, специального поведения и т. Д.

Конечно, я могу частично понять, почему разработчики языка решают так, как они делают: экземпляры классов имеют тенденцию иметь некоторые пространственные издержки (потому что экземпляры могут содержать vtable или другие метаданные в их макете памяти), что примитивам / структурам не нужно есть (если язык не разрешает наследование на тех).

Является ли пространственная эффективность (и улучшенная пространственная локальность, особенно в больших массивах) единственной причиной, по которой фундаментальные типы часто не являются классами?

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

Это выше, или я что-то упускаю?

Теодорос Чатзигианнакис
источник

Ответы:

19

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

Во-первых, это не просто «пространственные накладные расходы». Создание примитивов в штучной упаковке / выделенных в куче также снижает производительность. Существует дополнительное давление на GC, чтобы распределить и собрать эти объекты. Это идет вдвойне, если «примитивные объекты» неизменны, как и должно быть. Кроме того, происходит больше пропусков кеша (как из-за косвенности, так и из-за того, что меньше данных помещается в заданный объем кеша). Плюс сам факт, что «загрузить адрес объекта, а затем загрузить фактическое значение с этого адреса» требует больше инструкций, чем «загрузить значение напрямую».

Во-вторых, анализ побега - это не просто волшебная пыль. Это относится только к ценностям, которые, ну, не избежать. Конечно, приятно оптимизировать локальные вычисления (такие как счетчики циклов и промежуточные результаты вычислений), и это даст ощутимые преимущества. Но гораздо большее большинство значений живет в полях объектов и массивов. Конечно, они могут быть самим объектом анализа выхода, но так как они обычно являются изменяемыми ссылочными типами, любое их совмещение имен представляет собой серьезную проблему для анализа выхода, который теперь должен доказать, что эти псевдонимы (1) тоже не избегают и (2) не имеют значения с целью устранения распределения.

Учитывая, что вызов любого метода (включая методы получения) или передача объекта в качестве аргумента любому другому методу может помочь избежать объекта, вам потребуется межпроцедурный анализ во всех случаях, кроме самых тривиальных. Это намного дороже и сложнее.

И затем есть случаи, когда вещи действительно убегают и не могут быть разумно оптимизированы. На самом деле, их довольно много, если учесть, как часто программисты на С сталкиваются с проблемой распределения кучи. Когда объект, содержащий int, экранируется, анализ escape также перестает применяться к int. Попрощайся с эффективными примитивными полями .

Это связано с еще одним моментом: требуемый анализ и оптимизация серьезно усложняются и являются активной областью исследований. Это спорно ли когда-либо любая реализация языка достигается степень оптимизации вы предлагаете, и даже если это так, это было редкое и титанические усилия. Конечно, стоять на плечах этих гигантов легче, чем быть самим гигантом, но это все еще далеко от тривиальности. Не ожидайте конкурентных результатов в любое время в первые несколько лет, если вообще когда-либо.

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


источник
Говоря об эвакуационном анализе, я также имел в виду выделение для автоматического хранения (оно не решает все, но, как вы говорите, решает некоторые вещи). Я также признаю, что недооценил степень, в которой поля и псевдонимы могут приводить к сбоям при анализе побега. Больше всего меня беспокоит промах кэша, когда я говорю о пространственной эффективности, так что спасибо за решение этого вопроса.
Теодорос Чатзигианнакис
@TheodorosChatzigiannakis Я включаю изменение стратегии распределения в анализ побега (потому что, честно говоря, это единственное, для чего он когда-либо использовался).
Ваш второй абзац: объекты не всегда должны быть распределены в куче или иметь ссылочные типы. Фактически, когда это не так, это делает необходимые оптимизации сравнительно легкими. Смотрите ранний пример для объектов, выделенных из стека C ++, и систему владения Rust, чтобы узнать, как внедрить анализ escape непосредственно в язык.
Амон
@amon Я знаю, и, возможно, мне следовало бы прояснить это, но кажется, что OP интересуется только Java- и C # -подобными языками, где выделение кучи является почти обязательным (и неявным) из-за семантики ссылок и приведения без потерь между подтипами. Хорошая мысль о том, что Rust использует то, что обходится без анализа!
@delnan Это правда. Мне в основном интересны языки, которые абстрагируются от деталей хранилища, но, пожалуйста, не стесняйтесь включать все, что вы считаете актуальным, даже если это не применимо к этим языкам.
Теодорос Chatzigiannakis
27

Является ли пространственная эффективность (и улучшенная пространственная локальность, особенно в больших массивах) единственной причиной, по которой фундаментальные типы часто не являются классами?

Нет.

Другая проблема заключается в том, что фундаментальные типы, как правило, используются фундаментальными операциями. Компилятор должен знать, что int + intон собирается не для вызова функции, а для какой-то элементарной инструкции процессора (или эквивалентного байт-кода). В этот момент, если у вас есть intобычный объект, вам все равно придется эффективно его распаковать.

Подобные операции также не очень хорошо работают с подтипами. Вы не можете отправить к инструкции процессора. Вы не можете отправить из инструкции процессора. Я имею в виду, что весь смысл подтипирования заключается в том, что вы можете использовать там, Dгде можете B. Инструкции процессора не являются полиморфными. Чтобы заставить примитивы сделать это, вы должны обернуть их операции логикой диспетчеризации, которая в несколько раз превышает количество операций как простое дополнение (или что-то еще). Преимущество intбыть частью иерархии типов становится немного спорным, когда оно запечатано / окончательно. И это игнорирует все головные боли с логикой диспетчеризации для бинарных операторов ...

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

Telastyn
источник
4
Проверьте реализацию любого из динамически типизированных языков, которые обрабатывают целые числа и, например, объекты. Последняя примитивная инструкция ЦП может быть очень хорошо спрятана в методе (перегрузка оператора) в реализации класса с единственными привилегиями в библиотеке времени выполнения. Детали будут выглядеть по-разному с системой статического типа и компилятором, но это не является фундаментальной проблемой. В худшем случае это только делает вещи еще медленнее.
3
int + intможет быть обычным оператором языкового уровня, который вызывает встроенную инструкцию, которая гарантированно компилируется (или ведет себя как) в операторе добавления целочисленного собственного процессора. Преимущество intнаследования от objectне только возможности наследования другого типа от int, но также и возможности intповедения objectбез бокса. Рассмотрим дженерики C #: вы можете иметь ковариацию и контравариантность, но они применимы только к типам классов - типы структур автоматически исключаются, потому что они могут стать только objectчерез (неявный, сгенерированный компилятором) бокс.
Теодорос Чатзигианнакис
3
@delnan - конечно, хотя в моем опыте со статически типизированными реализациями, так как каждый несистемный вызов сводится к примитивным операциям, их накладные расходы оказывают существенное влияние на производительность - что, в свою очередь, оказывает еще более существенное влияние на принятие.
Теластин
@TheodorosChatzigiannakis - отлично, так что вы можете получить дисперсию и контравариантность для типов, которые не имеют полезного суб / супертипа ... А реализация этого специального оператора для вызова инструкции ЦП все еще делает его особенным. Я не согласен с этой идеей - я делал очень похожие вещи на своих игрушечных языках, но я обнаружил, что во время реализации есть практические ошибки, которые не делают такие вещи такими чистыми, как вы ожидаете.
Теластин
1
@TheodorosChatzigiannakis Внесение через границы библиотеки, безусловно, возможно, хотя это еще один элемент в списке покупок «Оптимизация высокого класса, который я хотел бы иметь». Я чувствую себя обязанным указать на то, что общеизвестно сложно получить полное право, не будучи настолько консервативным, чтобы быть бесполезным.
4

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

  • Вы хотите, чтобы определяемые пользователем типы могли наследоваться от фундаментальных типов. Обычно это нежелательно, так как создает проблемы, связанные с производительностью и безопасностью. Это проблема производительности, потому что компиляция не может предполагать, что intбудет иметь определенный фиксированный размер или что никакие методы не были переопределены, и это проблема безопасности, потому что семантика ints может быть подорвана (рассмотрим целое число, равное любому числу, или что меняет свою ценность, а не быть неизменным).

  • У ваших примитивных типов есть супертипы, и вы хотите иметь переменные с типом супертипа примитивного типа. Например, предположим, что у вас есть ints Hashable, и вы хотите объявить функцию, которая принимает Hashableпараметр, который может принимать как обычные объекты, так и ints.

    Это можно «решить», сделав такие типы недопустимыми: избавьтесь от подтипов и решите, что интерфейсы - это не типы, а ограничения типов. Очевидно, что это снижает выразительность вашей системы типов, и такую ​​систему типов больше нельзя было бы назвать объектно-ориентированной. Смотрите Haskell для языка, который использует эту стратегию. C ++ находится на полпути, потому что примитивные типы не имеют супертипов.

    Альтернатива - полный или частичный бокс основных типов. Тип бокса не должен быть видимым для пользователя. По сути, вы определяете внутренний коробочный тип для каждого фундаментального типа и неявные преобразования между коробочным и фундаментальным типом. Это может быть неудобно, если в штучной упаковке разные семантики. В Java есть две проблемы: у коробочных типов есть понятие идентичности, тогда как у примитивов есть только концепция эквивалентности значений, а у коробчатых типов можно обнуляться, тогда как примитивы всегда допустимы. Этих проблем можно полностью избежать, не предлагая концепцию идентичности для типов значений, предлагая перегрузку операторов и не делая все объекты обнуляемыми по умолчанию.

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

Языки, которые имеют статическую типизацию, хорошо используют примитивные типы везде, где это возможно, и используют только коробочные типы в качестве крайней меры. Хотя многие программы не очень чувствительны к производительности, есть случаи, когда размер и структура примитивных типов чрезвычайно важны: подумайте о крупномасштабном сжатии чисел, когда вам нужно разместить миллиарды точек данных в памяти. Переключение с doubleнаfloatможет быть жизнеспособной стратегией оптимизации пространства в C, но она не будет иметь никакого эффекта, если все числовые типы будут всегда упакованы (и, следовательно, тратят по меньшей мере половину своей памяти на указатель механизма диспетчеризации). Когда примитивные типы в штучной упаковке используются локально, убрать бокс с помощью встроенных функций компилятора довольно просто, но было бы недальновидно ставить общую производительность вашего языка на «достаточно продвинутый компилятор».

Амон
источник
intВряд ли неизменная на всех языках.
Скотт Уитлок
6
@ScottWhitlock Я понимаю, почему вы можете так думать, но в целом примитивные типы являются неизменяемыми типами значений. Ни один здравомыслящий язык не позволяет изменить значение числа семь. Однако многие языки позволяют переназначить переменную, которая содержит значение типа примитива, на другое значение. В C-подобных языках переменная является именованной ячейкой памяти и действует как указатель. Переменная не совпадает со значением, на которое она указывает. intЗначение является неизменным, но intпеременная не является.
Амон
1
@amon: нет вменяемого языка; просто Java: thedailywtf.com/articles/Disgruntled-Bomb-Java-Edition
Мейсон Уилер,
get rid of subtyping and decide that interfaces aren't types but type constraints.... such a type system wouldn't be called object-oriented any longer но это звучит как программирование на основе прототипов, что определенно ООП.
Майкл
1
@ScottWhitlock, вопрос в том, можете ли вы, если у вас тогда int b = a, сделать что-то для b, что изменит значение a. Существовали некоторые языковые реализации, где это возможно, но это обычно считается патологическим и нежелательным, в отличие от того же самого для массива.
Random832
2

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

  • неизменность
  • Окончательность (невозможно получить из)
  • Статическая печать

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

Это добавляет изрядную обработку особых случаев в компиляторе, но это не ограничивается каким-то мифическим супер-продвинутым компилятором. Эта оптимизация в реальных производственных компиляторах на основных языках. Scala даже позволяет вам определять свои собственные классы значений.

Карл Билефельдт
источник
1

В Smalltalk все они (int, float и т. Д.) Являются объектами первого класса. Только особый случай, SmallIntegers кодифицированы и трактуются по- разному виртуальной машины ради эффективности, и , следовательно , класс SmallInteger не допустят подклассы (который не является практическим ограничение.) Обратите внимание , что это не требует какого - либо особого внимания со стороны программиста, поскольку различие ограничено автоматическими процедурами, такими как генерация кода или сборка мусора.

И компилятор Smalltalk (исходный код -> байт-коды VM), и нативизатор VM (байт-коды -> машинный код) оптимизируют сгенерированный код (JIT), чтобы уменьшить количество элементарных операций с этими базовыми объектами.

Леандро Канилья
источник
1

Я проектировал OO langauge и runtime (это не удалось по совершенно разным причинам).

Нет ничего изначально неправильного в создании таких вещей, как настоящие классы; на самом деле это облегчает проектирование GC, поскольку теперь существует только 2 вида заголовков кучи (класс и массив), а не 3 (класс, массив и примитив) [тот факт, что мы можем объединить класс и массив после этого, не имеет значения ].

Действительно важный случай, когда у примитивных типов должны быть в основном финальные / запечатанные методы (+ действительно имеет значение, ToString не так уж и много). Это позволяет компилятору статически разрешать практически все вызовы самих функций и вставлять их в строку. В большинстве случаев это не имеет значения, как при копировании (я решил сделать встраивание доступным на уровне языка [как и в .NET]), но в некоторых случаях, если методы не запечатаны, компилятор будет вынужден сгенерировать вызов функция, используемая для реализации int + int.

Джошуа
источник