Сравнение операционного выполнения подстроки между.NET и Java
Взятие подстрок строки является очень общей операцией обработки строк, но я слышал, что могли бы быть существенные различия в производительности/реализации между платформой.NET и Java. Конкретно я слышал это в Java, java.lang.String предложения постоянная операция времени для substring, но в.NET, System.String предлагает линейную производительность Substring.
Эти действительно имеют место? Это может быть подтверждено в документации/исходном коде и т.д.? Действительно ли эта реализация конкретна, или указанная языком и/или платформой? Каковы за и против каждого подхода? Что должно, человек, мигрирующий от одной платформы до другого, ищет, чтобы не попадать в какие-либо ловушки производительности?
4 ответа
В .NET, Substring является O(n), а не O(1) из Java. Это связано с тем, что в .NET объект String сам содержит все фактические символьные данные1 - поэтому взятие подстроки включает копирование всех данных в новую подстроку. В Java substring может просто создать новый объект, ссылающийся на исходный массив char, с другим начальным индексом и длиной.
У каждого подхода есть свои плюсы и минусы:
- подход NET имеет лучшую когерентность кэша, создает меньше объектов 2 и позволяет избежать ситуации, когда одна маленькая подстрока предотвращает сборку в мусор очень большого
char[]. Я полагаю, что в некоторых случаях это также может упростить взаимодействие. - Подход Java делает взятие подстроки очень эффективным, и, вероятно, некоторые другие операции тоже
Есть немного больше деталей в моей статье strings.
Что касается общего вопроса о том, как избежать ловушек производительности, я думаю, что у меня должен быть готовый ответ, который можно вырезать и вставить: убедитесь, что ваша архитектура эффективна, и реализуйте ее наиболее читаемым способом. Измерьте производительность и оптимизируйте там, где вы найдете узкие места.
1 Кстати, это делает string очень особенным - это единственный не-массивный тип, чей объем памяти меняется в зависимости от экземпляра в рамках одной и той же CLR.
2 Для маленьких строк это большая победа. Достаточно плохо, что все накладные расходы приходятся на один объект, но когда к этому добавляется еще и массив, строка из одного символа может занять в Java около 36 байт. (Это число "на пальцах" - я не могу вспомнить точные накладные расходы на объекты. Это также зависит от используемой вами виртуальной машины.)
.Это действительно зависит от вашей нагрузки. Если вы зацикливаетесь и выполняете много вызовов подстроки, у вас могут возникнуть проблемы. Что касается сообщения SO, о котором вы говорите, я сомневаюсь, что это когда-либо будет проблемой. Однако с таким отношением вы всегда можете оказаться в ситуации «смерти от тысячи сокращений». В сообщении SO, на которое вы ссылаетесь, у нас есть следующее:
String after = before.Substring(0, 1).ToUpper() + before.Substring(1);
Предполагая, что компилятор не выполняет сумасшедших оптимизаций, это создаст по крайней мере четыре новых строки (2 вызова Substring , ToUpper и конкатенация). Подстрока реализована точно так, как вы ожидали (копия строки), но три из этих строк, выделенных выше, быстро станут мусором. Это создаст ненужную нагрузку на память. Я говорю «ненужный», потому что вы, вероятно, сможете найти более экономичное решение, потратив лишь немного больше времени.
В конце концов, профайлер - ваш лучший друг :)
Используя рефлектор, вы получите от Substring (Int32, Int32)
[SecuritySafeCritical, TargetedPatchingOptOut("Performance critical to inline across NGen image boundaries")]
public string Substring(int startIndex, int length)
{
return this.InternalSubStringWithChecks(startIndex, length, false);
}
, если продолжаете идти внутрь последний вызов - к
internal static unsafe void wstrcpy(char* dmem, char* smem, int charCount)
, который копирует символы с помощью указателей. Полный код на самом деле выглядит большим, но вы не увидите, насколько он медленный или быстрый, пока вы не запустите его и не протестируете.