Могут ли современные языки OO конкурировать с производительностью хранилища массивов в C ++?

Я только что заметил, что каждый современный язык программирования ОО, с которым я, по крайней мере, немного знаком (в основном это просто Java, C # и D), допускает ковариантные массивы. То есть массив строк - это массив объектов:

Object[] arr = new String[2];   // Java, C# and D allow this

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

arr[0] = "hello";        // ok
arr[1] = new Object();   // ArrayStoreException

Это кажется ужасным ударом по производительности, если я делаю много магазинов массивов.

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

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

arr[1] = arr[0];

Можно утверждать, что магазин не может выйти из строя. Я уверен, что есть много других возможных оптимизаций, о которых я не думал.

Действительно ли современные компиляторы выполняют такие виды оптимизации, или мне приходится мириться с тем фактом, что, например, Quicksort всегда выполняет O (n log n) ненужные проверки во время выполнения?

Могут ли современные ОО-языки избежать накладных расходов, создаваемых за счет поддержки ко-вариантных массивов?

У D нет ковариантных массивов. Это позволило им до самой последней версии ( dmd 2.057 ), но эта ошибка была исправлена.

Массив в D - это просто структура с указателем и длиной:

struct A(T)
{
    T* ptr;
    size_t length;
}

Проверка границ выполняется обычно при индексации массива, но она удаляется при компиляции -release. Таким образом, в режиме релиза нет никакой реальной разницы в производительности между массивами в C / C ++ и массивами в D.

Да, одна важная оптимизация заключается в следующем:

sealed class Foo
{
}

В C # этот класс не может быть супертипом для любого типа, поэтому вы можете избежать проверки для массива типа Foo.

И ко второму вопросу, в F # совместные варианты недопустимы (но я думаю, что проверка останется в CLR, если она не будет сочтена ненужной при оптимизации во время выполнения)

let a = [| "st" |]
let b : System.Object[] = a // Fails

https://stackoverflow.com/questions/7339013/array-covariance-in-f

Несколько связанная проблема - проверка границ массива. Это может быть интересное (но старое) чтение об оптимизации, выполненной в CLR (ковариация также упоминается 1 место): http://blogs.msdn.com/b/clrcodegeneration/archive/2009/08/13/array-bounds -check-элиминирования-в-clr.aspx

Java ответ:

Я так понимаю, вы на самом деле не тестировали код, не так ли? В общем, 90% всех динамических приведений в Java бесплатны, потому что JIT может их исключить (быстрая сортировка должна быть хорошим примером для этого), а остальные представляют собой одну ld/cmp/brпоследовательность, которая абсолютно предсказуема (если нет, то почему, черт возьми, ваш код бросает) все эти исключения динамического приведения?).

Мы выполняем загрузку намного раньше, чем фактическое сравнение, ветвь правильно предсказана в 99,9999% (составленная статистика!) Всех случаев, поэтому мы не останавливаем конвейер (при условии, что мы не попадаем в память с нагрузкой, если не хорошо, что будет заметно, но тогда нагрузка все равно нужна). Следовательно, стоимость составляет 1 такт, если JIT вообще не может избежать проверки.

Некоторые накладные расходы? Конечно, но я сомневаюсь, что вы когда-нибудь заметите это ..

Чтобы поддержать мой ответ, посетите этот пост в блоге Dr. Cliff Click, где обсуждается производительность Java и C.

D не допускает ковариантные массивы.

void main()
{
    class Foo {}
    Object[] a = new Foo[10];
}  

/* Error: cannot implicitly convert expression (new Foo[](10LU)) of type Foo[]
to Object[] */

Как вы говорите, это было бы дырой в системе типов, чтобы позволить это.

Вы можете быть прощены за ошибку, поскольку эта ошибка была исправлена только в самой последней версии DMD, выпущенной 13 декабря.

Доступ к массиву в D такой же быстрый, как в C или C ++.

Из теста, который я сделал на дешевом ноутбуке, разница между использованием int[]и Integer[]составляет около 1,0 нс. Разница может быть связана с дополнительной проверкой типа.

Обычно объекты используются только для логики более высокого уровня, когда не каждый ns имеет значение. Если вам нужно сохранять каждые ns, я бы не использовал конструкции более высокого уровня, такие как Objects. Одни только задания, вероятно, будут очень маленьким фактором в любой реальной программе. например, создание нового объекта на той же машине - 5 нс.

Вызовы CompareTo, вероятно, будут намного дороже, особенно если вы используете сложный объект, такой как String.

Вы спрашивали о других современных языках ОО? Что ж, Delphi полностью избегает этой проблемы, будучи stringпримитивом, а не объектом. Таким образом, массив строк - это в точности массив строк и ничего более, и любые операции над ними выполняются настолько быстро, насколько это возможно для нативного кода, без дополнительных проверок типов.

Однако строковые массивы используются не очень часто; Программисты Delphi предпочитают TStringListкласс. Для минимальных накладных расходов он предоставляет набор методов группы строк, которые полезны во многих ситуациях, когда класс сравнивают со швейцарским армейским ножом. Поэтому идиоматично использовать объект списка строк вместо массива строк.

Что касается других объектов в целом, проблема не существует, потому что в Delphi, как и в C ++, массивы не являются ковариантными, чтобы предотвратить описанные здесь дыры в системе типов.

или я должен смириться с тем, что, например, Quicksort всегда делает O (n log n) ненужные проверки во время выполнения?

Производительность процессора не монотонна, что означает, что более длинные программы могут быть быстрее, чем более короткие (это зависит от процессора, и это справедливо для обычных архитектур x86 и amd64). Таким образом, вполне возможно, что программа, выполняющая проверку границ массивов, на самом деле быстрее, чем программа, выведенная из предыдущей путем удаления этих проверок границ.

Причина такого поведения заключается в том, что проверка границ изменяет выравнивание кода в памяти, изменяет частоту обращений к кешу и т. Д.

Так что да, смиритесь с тем, что Quicksort всегда делает O (n log n) ложных проверок и оптимизирует после профилирования.

Scala - это ОО-язык, который имеет инвариантные, а не ковариантные массивы. Он нацелен на JVM, поэтому здесь нет выигрыша в производительности, но он избегает ошибочных характеристик, общих для Java и C #, что ставит под угрозу их безопасность типов по причинам обратной совместимости.