Русский
Русский
English
Статистика
Реклама

Строки

Перевод Приёмы и хитрости начинающего Java-программиста

05.10.2020 10:14:40 | Автор: admin

Небольшая коллекция практик, трюков и подсказок, с помощью которых вы сэкономите своё время при изучении Java и написании кода на этом языке программирования. Перевод статьиTop 25 Java Tricks, Tips, and Best Practices от специалистов Рексофт.

Организация работы

Чистый код

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

  • Правило 10-50-500. В одном пакете не может быть более 10 классов. Каждый метод должен быть короче 50 строк кода, а каждый класс короче 500 строк.

  • SOLID принципы.

  • Использование паттернов проектирования.

Работа с ошибками

Stack Trace (Трассировка стека)

Выявление ошибок это, пожалуй, самая трудоемкая часть процесса разработки на Java. Трассировка стека позволяет вам точно отслеживать, где именно в проекте возникла ошибка или исключение (exception).

import java.io.*;Exception e = ;java.io.StringWriter sw = new java.io.StringWriter();e.printStackTrace(new java.io.PrintWriter(sw));String trace = sw.getBuffer().toString();

NullPointerException

Исключения, возникающие из-заnullзначений (NullPointerException), довольно часто появляются при попытке вызвать метод у несуществующего объекта.

Возьмем для примера следующий код:

int noOfStudents = school.listStudents().count;private int getListOfStudents(File[] files) {if (files == null)  throw new NullPointerException("File list cannot be null");}

Примечание переводчика: а вот пример от меня как переводчика материала:

String anyString = null;if (anyString.equals("some string")) { // здесь будет null pointer exception, т.к. anyString == null// ...}

Дата и Время

System.currentTimeMillis или System.nanoTime?

В Java есть два стандартных способа проведения операций со временем, и не всегда ясно, какой из них следует выбрать.

МетодSystem.currentTimeMillis()возвращает текущее количество миллисекунд с начала эры Unix в формате Long. Его точность составляет от 1 до 15 тысячных долей секунды в зависимости от системы.

long startTime = System.currentTimeMillis();long estimatedTime = System.currentTimeMillis() - startTime;

МетодSystem.nanoTime()имеет точность до одной миллионной секунды (наносекунды) и возвращает текущее значение наиболее точного доступного системного таймера.

long startTime = System.nanoTime();long estimatedTime = System.nanoTime() - startTime;

Таким образом, методSystem.currentTimeMillis()лучше применять для отображения и синхронизации абсолютного времени, аSystem.nanoTime()для измерения относительных интервалов времени.

Валидация Даты из строки

Если необходимо достать объектDateиз обычной строки в Java, можете использовать небольшой утилитный класс, который приведен ниже. Он позаботится обо всех сложностях валидации и преобразовании строки в объектDate.

package net.viralpatel.java;import java.text.ParseException;import java.text.SimpleDateFormat;import java.util.ArrayList;import java.util.Date;import java.util.List;public class DateUtil {// List of all date formats that we want to parse.// Add your own format here.private static List; dateFormats = new ArrayList() {{add(new SimpleDateFormat("M/dd/yyyy"));add(new SimpleDateFormat("dd.M.yyyy"));add(new SimpleDateFormat("M/dd/yyyy hh:mm:ss a"));add(new SimpleDateFormat("dd.M.yyyy hh:mm:ss a"));add(new SimpleDateFormat("dd.MMM.yyyy"));add(new SimpleDateFormat("dd-MMM-yyyy"));}};/** * Convert String with various formats into java.util.Date *  * @param input *            Date as a string * @return java.util.Date object if input string is parsed  * successfully else returns null */public static Date convertToDate(String input) {Date date = null;if(null == input) {return null;}for (SimpleDateFormat format : dateFormats) {try {format.setLenient(false);date = format.parse(input);} catch (ParseException e) {//Shhh.. try other formats}if (date != null) {break;}}return date;}}

Пример его использования:

package net.viralpatel.java;public class TestDateUtil {public static void main(String[] args) {System.out.println("10/14/2012" + " = " + DateUtil.convertToDate("10/14/2012"));System.out.println("10-Jan-2012" + " = " + DateUtil.convertToDate("10-Jan-2012"));System.out.println("01.03.2002" + " = " + DateUtil.convertToDate("01.03.2002"));System.out.println("12/03/2010" + " = " + DateUtil.convertToDate("12/03/2010"));System.out.println("19.Feb.2011" + " = " + DateUtil.convertToDate("19.Feb.2011" ));System.out.println("4/20/2012" + " = " + DateUtil.convertToDate("4/20/2012"));System.out.println("some string" + " = " + DateUtil.convertToDate("some string"));System.out.println("123456" + " = " + DateUtil.convertToDate("123456"));System.out.println("null" + " = " + DateUtil.convertToDate(null));}}

Результат:

10/14/2012 = Sun Oct 14 00:00:00 CEST 201210-Jan-2012 = Tue Jan 10 00:00:00 CET 201201.03.2002 = Fri Mar 01 00:00:00 CET 200212/03/2010 = Fri Dec 03 00:00:00 CET 201019.Feb.2011 = Sat Feb 19 00:00:00 CET 20114/20/2012 = Fri Apr 20 00:00:00 CEST 2012some string = null123456 = nullnull = null

Строки

Оптимизация строки

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

Необходимо избегать создания Java строк через конструктор, пример:

// медленное создание строкиString bad = new String ("Yet another string object");// быстрое создание строкиString good = "Yet another string object"

Одинарные и двойные кавычки

Что ты ожидаешь в результате выполнения этого кода?

public class Haha {  public static void main(String args[]) {    System.out.print("H" + "a");    System.out.print('H' + 'a');  }}

Казалось бы, строка должна возвращать HaHa, но на самом деле это будет Ha169.

Двойные кавычки обрабатывают символы как строки, но одинарные кавычки ведут себя иначе. Они преобразуют символьные операнды ('H'и'a') в целые значения посредством расширения примитивных типов получается 169.

Математика

Float или Double?

Программисты часто не могут выбрать необходимую точность для чисел с плавающей запятой. Float требует всего 4 байта, но имеет только 7 значащих цифр, а Double в два раза точнее (15 цифр), но в два раза прожорливее.

Фактически, большинство процессоров могут одинаково эффективно работать как с Float, так и с Double, поэтому воспользуйтесь рекомендацией Бьорна Страуструпа (автор языка С++):

Выбор правильной точности для решения реальных задач требует хорошего понимания природы машинных вычислений. Если у вас его нет, либо посоветуйтесь с кем-нибудь, либо изучите проблему самостоятельно, либо используйте Double и надейтесь на лучшее.

Проверка на нечетность

Можно ли использовать этот код для точного определения нечетного числа?

public boolean oddOrNot(int num) {  return num % 2 == 1;}

Надеюсь, вы заметили хитрость. Если мы решим таким образом проверить отрицательное нечетное число (например, -5), остаток от деления не будет равен единице, поэтому воспользуйтесь более точным методом:

public boolean oddOrNot(int num) {  return (num & 1) != 0;}

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

Возведение в степень

Возвести число в степень можно двумя способами:

  1. простое умножение;

  2. используя методMath.pow()(двойное основание, двойной показатель степени).

Использование библиотечной функции рекомендуется только в случае крайней необходимости, например, в случае дробной или отрицательной степени.

double result = Math.pow(625, 0.5); // 25.0

Простое умножение в Java работает в 300-600 раз эффективнее, кроме того, его можно дополнительно оптимизировать:

double square = double a * double a;  double cube = double a * double a * double a; // не оптимизированоdouble cube = double a * double square;  // оптимизировано double quad = double a * double a * double a * double a; // не оптимизированоdouble quad = double square * double square; // оптимизировано

JIT оптимизация

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

В качестве примера рассмотрим две простые операции:

// 1n += 2 * i * i; // 2n += 2 * (i * i);

Давайте измерим время выполнения каждого из них:

// 1long startTime1 = System.nanoTime(); int n1 = 0; for (int i = 0; i < 1000000000; i++) {   n1 += 2 * i * i; } double resultTime1 = (double)(System.nanoTime() - startTime1) / 1000000000;System.out.println(resultTime1 + " s");  // 2long startTime2 = System.nanoTime(); int n2 = 0; for (int i = 0; i < 1000000000; i++) {   n2 += 2 * (i * i); } double resultTime2 = (double)(System.nanoTime() - startTime2) / 1000000000;System.out.println(resultTime2 + " s");

Запустив этот код несколько раз, мы получим примерно следующее:

|`2*(i*i)`| `2*i*i`||---------|--------||0.5183738 | 0.6246434||0.5298337 | 0.6049722||0.5308647 | 0.6603363||0.5133458 | 0.6243328||0.5003011 | 0.6541802||0.5366181 | 0.6312638||0.515149  | 0.6241105||0.5237389 | 0.627815 ||0.5249942 | 0.6114252||0.5641624 | 0.6781033||0.538412  | 0.6393969||0.5466744 | 0.6608845||0.531159  | 0.6201077||0.5048032 | 0.6511559||0.5232789 | 0.6544526|

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

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

Структуры данных

Комбинирование хеш-таблиц

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

import java.util.*;Map m1 = ;Map m2 = ;m2.putAll(m1); // добавить к m2 все элементы из m1

Array или ArrayList?

Выбор междуArrayиArrayListзависит от специфики задачи Java, которую вы хотите решить. Запомните следующие особенности этих типов:

  • Массив имеет фиксированный размер, и память для него выделяется во время объявления, а размерArrayListможет динамически меняться.

  • Массивы Java работают намного быстрее, а вArrayListнамного проще добавлять и удалять элементы.

  • При работе сArrayскорее всего возникнет ошибкаArrayIndexOutOfBoundsException.

  • ArrayList может быть только одномерным, когда массивы Java могут быть многомерными.

import java.util.*; public class ArrayVsArrayList {  public static void main(String[] args) {    // создаем массив    int[] myArray = new int[6];     // ссылаемся на несуществующий индекс    myArray[7]= 10; // ArrayIndexOutOfBoundsException     // создаем ArrayList    List myArrayList = new ArrayList<>();     // простое добавление и удаление элементов    myArrayList.add(1);    myArrayList.add(2);    myArrayList.add(3);    myArrayList.add(4);    myArrayList.add(5);    myArrayList.remove(0);     // перебор элементов ArrayList     for(int i = 0; i < myArrayList.size(); i++) {      System.out.println("Element: " + myArrayList.get(i));    }     //  многомерный массив    int[][][] multiArray = new int[3][3][3];   }}

JSON

Сериализация и Десериализация

JSON невероятно удобный и полезный синтаксис для хранения и обмена данными. Java полностью поддерживает это.

Примечание переводчика: для использования JSON из примера необходимо подключить библиотекуJSON Simple.

Вы можете сериализовать данные следующим образом:

import org.json.simple.JSONObject;import org.json.simple.JSONArray; public class JsonEncodeDemo {  public static void main(String[] args) {    JSONObject obj = new JSONObject();    obj.put("Novel Name", "Godaan");    obj.put("Author", "Munshi Premchand");     JSONArray novelDetails = new JSONArray();    novelDetails.add("Language: Hindi");    novelDetails.add("Year of Publication: 1936");    novelDetails.add("Publisher: Lokmanya Press");            obj.put("Novel Details", novelDetails);      System.out.print(obj);    }}

Получается следующая строка JSON:

{"Novel Name":"Godaan","Novel Details":["Language: Hindi","Year of Publication: 1936","Publisher: Lokmanya Press"],"Author":"Munshi Premchand"}

Десериализация в Java выглядит так:

import java.io.FileNotFoundException;import java.io.FileReader;import java.io.IOException;import java.util.Iterator; import org.json.simple.JSONArray;import org.json.simple.JSONObject;import org.json.simple.parser.JSONParser;import org.json.simple.parser.ParseException; public class JsonParseTest {  private static final String filePath = "//home//user//Documents//jsonDemoFile.json";      public static void main(String[] args) {    try {      // читаем json файл      FileReader reader = new FileReader(filePath);      JSONParser jsonParser = new JSONParser();      JSONObject jsonObject = (JSONObject)jsonParser.parse(reader);                  // берем данные из json объекта      Long id =  (Long) jsonObject.get("id");      System.out.println("The id is: " + id);                  String type = (String) jsonObject.get("type");      System.out.println("The type is: " + type);       String name = (String) jsonObject.get("name");      System.out.println("The name is: " + name);       Double ppu =  (Double) jsonObject.get("ppu");      System.out.println("The PPU is: " + ppu);       // извлекаем массив              System.out.println("Batters:");      JSONArray batterArray= (JSONArray) jsonObject.get("batters");      Iterator i = batterArray.iterator();            // проходимся по всем элементам массива      while (i.hasNext()) {        JSONObject innerObj = (JSONObject) i.next();        System.out.println("ID "+ innerObj.get("id") +             " type " + innerObj.get("type"));      }       System.out.println("Topping:");      JSONArray toppingArray= (JSONArray) jsonObject.get("topping");      Iterator j = toppingArray.iterator();      while (j.hasNext()) {        JSONObject innerObj = (JSONObject) j.next();        System.out.println("ID "+ innerObj.get("id") +             " type " + innerObj.get("type"));      }    } catch (FileNotFoundException|IOException|ParseException|NullPointerException ex) {      ex.printStackTrace();    }  }}

Используемый в примере файл JSON (jsonDemoFile.json):

{  "id": 0001,  "type": "donut",  "name": "Cake",  "ppu": 0.55,  "batters":    [      { "id": 1001, "type": "Regular" },      { "id": 1002, "type": "Chocolate" },      { "id": 1003, "type": "Blueberry" },      { "id": 1004, "type": "Devil's Food" }    ],  "topping":    [      { "id": 5001, "type": "None" },      { "id": 5002, "type": "Glazed" },      { "id": 5005, "type": "Sugar" },      { "id": 5007, "type": "Powdered Sugar" },      { "id": 5006, "type": "Chocolate with Sprinkles" },      { "id": 5003, "type": "Chocolate" },      { "id": 5004, "type": "Maple" }    ]}

Примечание переводчика: в Java проектах очень часто для работы с JSON используют библиотеки Gson от Google или Jackson. Обе библиотеки очень популярны и хорошо поддерживаются. Попробуйте и их.

Ввод и Вывод

FileOutputStream или FileWriter?

Запись файлов в Java осуществляется двумя способами:FileOutputStreamиFileWriter. Какой метод выбрать, зависит от конкретной задачи.

FileOutputStreamпредназначен для записи необработанных байтовых потоков. Это делает его идеальным решением, например, для работы с изображениями.

File foutput = new File(file_location_string);FileOutputStream fos = new FileOutputStream(foutput);BufferedWriter output = new BufferedWriter(new OutputStreamWriter(fos));output.write("Buffered Content");

УFileWriterдругое призвание: работа с потоками символов. Поэтому, если вы пишете текстовые файлы, выберите этот метод.

FileWriter fstream = new FileWriter(file_location_string);BufferedWriter output = new BufferedWriter(fstream);output.write("Buffered Content");

Производительность и лучшие практики

Пустая коллекция вместо Null

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

import java.util.*public List getLocations() {  List result = someService.getLocationsFromDB();  return result == null ? Collections.emptyList() : result;}

Создание объектов только когда необходимо

Создание объектов одна из самых затратных операций в Java. Лучше всего создавать их только тогда, когда они действительно нужны.

import java.util.ArrayList;import java.util.List; public class Employees {  private List Employees;   public List getEmployees() {    // initialization only if necessary    if(null == Employees) {      Employees = new ArrayList();    }        return Employees;  }}

Deadlocks (Дедлоки)

Взаимная блокировка (Deadlock) потоков может происходить по многим причинам, и полностью защититься от них в Java 8 очень сложно. Чаще всего, это происходит, когда один синхронизируемый объект ожидает ресурсов, которые заблокированы другим синхронизированным объектом.

Вот пример тупика этого потока:

public class DeadlockDemo {  public static Object addLock = new Object();  public static Object subLock = new Object();   public static void main(String args[]) {    MyAdditionThread add = new MyAdditionThread();    MySubtractionThread sub = new MySubtractionThread();    add.start();    sub.start();  }   private static class MyAdditionThread extends Thread {    public void run() {      synchronized (addLock) {        int a = 10, b = 3;        int c = a + b;        System.out.println("Addition Thread: " + c);        System.out.println("Holding First Lock...");        try { Thread.sleep(10); }        catch (InterruptedException e) {}        System.out.println("Addition Thread: Waiting for AddLock...");        synchronized (subLock) {           System.out.println("Threads: Holding Add and Sub Locks...");        }      }    }  }   private static class MySubtractionThread extends Thread {    public void run() {      synchronized (subLock) {        int a = 10, b = 3;        int c = a - b;        System.out.println("Subtraction Thread: " + c);        System.out.println("Holding Second Lock...");        try { Thread.sleep(10); }        catch (InterruptedException e) {}        System.out.println("Subtraction  Thread: Waiting for SubLock...");        synchronized (addLock) {           System.out.println("Threads: Holding Add and Sub Locks...");        }      }    }  }}

Результат этой программы:

=====Addition Thread: 13Subtraction Thread: 7Holding First Lock...Holding Second Lock...Addition Thread: Waiting for AddLock...Subtraction  Thread: Waiting for SubLock...

Взаимоблокировок можно избежать, изменив порядок вызова потоков:

private static class MySubtractionThread extends Thread {  public void run() {    synchronized (addLock) {      int a = 10, b = 3;      int c = a - b;      System.out.println("Subtraction Thread: " + c);      System.out.println("Holding Second Lock...");      try { Thread.sleep(10); }      catch (InterruptedException e) {}      System.out.println("Subtraction  Thread: Waiting for SubLock...");      synchronized (subLock) {        System.out.println("Threads: Holding Add and Sub Locks...");      }    }  }}

Вывод:

=====Addition Thread: 13Holding First Lock...Addition Thread: Waiting for AddLock...Threads: Holding Add and Sub Locks...Subtraction Thread: 7Holding Second Lock...Subtraction  Thread: Waiting for SubLock...Threads: Holding Add and Sub Locks...

Резервирование памяти

Некоторые приложения Java очень ресурсоемки и могут работать медленно. Для повышения производительности вы можете выделить на машине Java больше оперативной памяти.

export JAVA_OPTS="$JAVA_OPTS -Xms5000m -Xmx6000m -XX:PermSize=1024m -XX:MaxPermSize=2048m"
  • Xms минимальный пул выделения памяти;

  • Xmx максимальный пул выделения памяти;

  • XX: PermSize начальный размер, который будет выделен при запуске JVM;

  • XX: MaxPermSize максимальный размер, который можно выделить при запуске JVM.

Примечание переводчика: PermSize и MaxPermSize, начиная с Java 8 уже больше не используются.

Решение распространенных проблем

Содержимое директории

Java позволяет вам получать имена всех подкаталогов и файлов в папке в виде массива, который затем можно последовательно прочитать:

import java.io.*; public class ListContents {  public static void main(String[] args) {    File file = new File("//home//user//Documents/");    String[] files = file.list();     System.out.println("Listing contents of " + file.getPath());    for(int i=0 ; i < files.length ; i++) {      System.out.println(files[i]);    }  }}

Выполнение консольных команд

Java позволяет выполнять консольные команды прямо из кода, используя классRuntime. Очень важно не забывать об обработке исключений.

Например, давайте попробуем открыть файл PDF через терминал Java (на Linuxe):

public class ShellCommandExec {  public static void main(String[] args) {    String gnomeOpenCommand = "gnome-open //home//user//Documents//MyDoc.pdf";     try {      Runtime rt = Runtime.getRuntime();      Process processObj = rt.exec(gnomeOpenCommand);       InputStream stdin = processObj.getErrorStream();      InputStreamReader isr = new InputStreamReader(stdin);      BufferedReader br = new BufferedReader(isr);       String myoutput = "";       while ((myoutput=br.readLine()) != null) {        myoutput = myoutput+"\n";      }      System.out.println(myoutput);    } catch (Exception e) {      e.printStackTrace();    }  }

Воспроизведение звуков

Звук важный компонент многих десктопных приложений и игр. Язык программирования Java предоставляет средства для работы с ним.

import java.io.*;import java.net.URL;import javax.sound.sampled.*;import javax.swing.*; public class PlaySoundDemo extends JFrame {    // constructor   public playSoundDemo() {      this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);      this.setTitle("Play Sound Demo");      this.setSize(300, 200);      this.setVisible(true);       try {         URL url = this.getClass().getResource("MyAudio.wav");         AudioInputStream audioIn = AudioSystem.getAudioInputStream(url);         Clip clip = AudioSystem.getClip();         clip.open(audioIn);         clip.start();      } catch (UnsupportedAudioFileException|IOException|LineUnavailableException e) {         e.printStackTrace();      }   }    public static void main(String[] args) {      new PlaySoundDemo();   }}

Отправка email

Отправить электронную почту на Java очень просто. Вам просто нужно установитьJava Mailи указать путь к нему в пути к классам проекта.

import java.util.*;import javax.mail.*;import javax.mail.internet.*; public class SendEmail {  public static void main(String [] args) {        String to = "recipient@gmail.com";    String from = "sender@gmail.com";    String host = "localhost";     Properties properties = System.getProperties();    properties.setProperty("mail.smtp.host", host);    Session session = Session.getDefaultInstance(properties);     try{      MimeMessage message = new MimeMessage(session);      message.setFrom(new InternetAddress(from));       message.addRecipient(Message.RecipientType.TO,new InternetAddress(to));       message.setSubject("My Email Subject");      message.setText("My Message Body");      Transport.send(message);      System.out.println("Sent successfully!");    } catch (MessagingException ex) {      ex.printStackTrace();    }  }}

Получение координат курсора

Чтобы фиксировать события мыши, вам необходимо реализовать интерфейсMouseMotionListener. Когда курсор попадает в определенную область, срабатывает обработчик событияmouseMoved, из которого вы можете получить точные координаты (используя Swing для UI)

import java.awt.event.*;import javax.swing.*; public class MouseCaptureDemo extends JFrame implements MouseMotionListener {  public JLabel mouseHoverStatus;   public static void main(String[] args) {    new MouseCaptureDemo();  }   MouseCaptureDemo() {    setSize(500, 500);    setTitle("Frame displaying Coordinates of Mouse Motion");     mouseHoverStatus = new JLabel("No Mouse Hover Detected.", JLabel.CENTER);    add(mouseHoverStatus);    addMouseMotionListener(this);    setVisible(true);  }   public void mouseMoved(MouseEvent e) {    mouseHoverStatus.setText("Mouse Cursor Coordinates => X:"+e.getX()+" | Y:"+e.getY());  }   public void mouseDragged(MouseEvent e) {  }}
Подробнее..

Ещё больше строковых оптимизаций

30.11.2020 18:20:43 | Автор: admin

В продолжение своей предыдущей статьи о строках (напоминаю, это была текстовая версия доклада на конференции JPoint-2020) решил дописать ещё одну заметку со строковыми оптимизациями, обнаруженными уже после вёрстки презентации (первые две есть на видео в самом конце, показывал их прямо из "Идеи").

Снова StringBuilder.append(char)

На сцене снова "Спринг", а именно o.s.u.StringUtils.deleteAny(String, String):

// org.springframework.util.StringUtilspublic static String deleteAny(String inString, String charsToDelete) {  if (!hasLength(inString) || !hasLength(charsToDelete)) {    return inString;  }  StringBuilder sb = new StringBuilder(inString.length());  for (int i = 0; i < inString.length(); i++) {    char c = inString.charAt(i);    if (charsToDelete.indexOf(c) == -1) {      sb.append(c);    }  }  return sb.toString();}

В разделе "Склейка: если всё-таки нужно" рассматривая StringBuilder.append(char) я отметил невозможность оптимизации компилятором проверок внутри этого метода даже в счётном цикле с заранее известным количеством проходов. Выходом станет использование массива.

Этот же подход хорошо ложится на случаи, в которых длина преобразованной строки может быть меньше или равна исходной. Действительно, какой бы аргумент не передавался в deleteAny, длина возвращаемой строки никогда не превысит длину исходной. Следовательно, можно незначительно усложнив код избавиться от SB:

public static String deleteAny(String inString, String charsToDelete) {  if (!hasLength(inString) || !hasLength(charsToDelete)) {    return inString;  }    int lastCharIndex = 0;  char[] result = new char[inString.length()];  for (int i = 0; i < inString.length(); i++) {    char c = inString.charAt(i);    if (charsToDelete.indexOf(c) == -1) {      result[lastCharIndex++] = c;    }  }  return new String(result, 0, lastCharIndex);}

Переменная lastCharIndex устраняет возможные "пустоты" в массиве при пропуске одного и более знаков.

Используя бенчмарк легко обнаруживаем существенный прирост производительности даже для небольших объёмов данных:

Benchmark                       Mode     Score     Error   Unitsoriginal                        avgt    90.203    4.317   ns/oppatched                         avgt    25.391    1.118   ns/oporiginal:gc.alloc.rate.norm    avgt   104.000    0.001    B/oppatched:gc.alloc.rate.norm     avgt   104.000    0.001    B/op

Но и это ещё не всё.

Уже после моего коммита наблюдательный пользователь Johnny Lim сообразил, что если после завершения перебора значение переменной lastCharIndex равно длине исходной строки, то ни одной замены не сделано, а значит новую строку создавать не нужно. Итого:

public static String deleteAny(String inString, String charsToDelete) {  if (!hasLength(inString) || !hasLength(charsToDelete)) {    return inString;  }    int lastCharIndex = 0;  char[] result = new char[inString.length()];  for (int i = 0; i < inString.length(); i++) {    char c = inString.charAt(i);    if (charsToDelete.indexOf(c) == -1) {      result[lastCharIndex++] = c;    }  }  if (lastCharIndex == inString.length()) {   // С - сообразительность    return inString;  }  return new String(result, 0, lastCharIndex);}

Похожий подход использован тут.

Коварный StringBuilder.append(Object)

Следующий пример намного менее очевиден:

// org.springframework.http.ContentDispositionprivate static String escapeQuotationsInFilename(String filename) {  if (filename.indexOf('"') == -1 && filename.indexOf('\\') == -1) {    return filename;  }  boolean escaped = false;  StringBuilder sb = new StringBuilder();  for (char c : filename.toCharArray()) {    sb.append((c == '"' && !escaped) ? "\\\"" : c);    // <----    escaped = (!escaped && c == '\\');  }  // Remove backslash at the end..  if (escaped) {    sb.deleteCharAt(sb.length() - 1);  }  return sb.toString();}

Больное место находится в строке 10, а заключение звучит так: поскольку тернарный оператор возвращает либо String, либо char, то аргументом метода StringBuilder.append() фактически является Object. И всё бы ничего, да преобразование знака в объект происходит с помощью String.valueOf() и мы на ровном месте получаем множество мелкого мусора по схеме:

Character.valueOf(c)   -> StringBuilder.append(Object)     -> String.valueOf()      -> Character.toString()

Отдельно доставляет реализация Character.toString:

Осторожно, не ушибите лицо ладонью
public final class Character {  private final char value;  public String toString() {    char buf[] = {value};    return String.valueOf(buf);  }}

Зачем было оборачивать знак в массив? Тайна сия велика... Как бы то ни было, это уже исправлено.

Таким образом, достаточно избавиться от тернарного оператора:

for (int i = 0; i < filename.length() ; i++) {  char c = filename.charAt(i);  if (!escaped && c == '"') {    sb.append("\\\"");    // append(String)  }  else {    sb.append(c);         // append(char)  }  escaped = (!escaped && c == '\\');}

И вновь очень простое изменение приносит впечатляющий прирост (бенчмарк по ссылке):

JDK 8Benchmark                             latin   len   Score          UnitsappendCovariant                        true    10   180.2  10.3   ns/opappendExact                            true    10    68.5   1.4   ns/opappendCovariant                       false    10   177.7   4.4   ns/opappendExact                           false    10    67.7   1.3   ns/opappendCovariant:gc.alloc.rate.norm    true    10   688.0   0.0    B/opappendExact:gc.alloc.rate.norm        true    10   112.0   0.0    B/opappendCovariant:gc.alloc.rate.norm   false    10   816.0   0.0    B/opappendExact:gc.alloc.rate.norm       false    10   112.0   0.0    B/opJDK 14Benchmark                             latin   len    Score         UnitsappendCovariant                        true    10    228.8  18.6  ns/opappendExact                            true    10     57.9   2.6  ns/opappendCovariant                       false    10    292.8  12.4  ns/opappendExact                           false    10     90.2   2.2  ns/opappendCovariant:gc.alloc.rate.norm    true    10    688.0   0.0   B/opappendExact:gc.alloc.rate.norm        true    10    112.0   0.0   B/opappendCovariant:gc.alloc.rate.norm   false    10   1096.0   0.0   B/opappendExact:gc.alloc.rate.norm       false    10    200.0   0.0   B/op

Обратите внимание, что исполнение не смогло выбросить мусорные объекты, хотя их область видимости крайне ограничена. Закономерно возникает вопрос: могёт ли Грааль?

Ответ

Не знаю, не проверял :)
Оставляю этот вопрос энтузиастам в качестве домашнего задания :)

Коварный String.substring

Давно известно, что метод String.substring всегда возвращает новую строку, и тем не менее в задачах на "выкусывание" он всё ещё пользуется незаслуженной популярностью:

// org.springframework.web.util.UrlPathHelper/** * Sanitize the given path replacing "//" with "/" */private String getSanitizedPath(String path) {  String sanitized = path;  while (true) {    int idx = sanitized.indexOf("//");    if (idx < 0) {      break;    }    else {      sanitized = sanitized.substring(0, idx) + sanitized.substring(idx + 1);    }  }  return sanitized;}

Здесь даже если исполнение каким-то чудом сможет распознать шаблон склеивания строк и подставить StringBuilder этот метод всё равно останется чертовски неэффективным.

В такого рода задачах очень важно посмотреть на алгоритм с высокого уровня и описать простыми словами выполняемую работу. Здесь получается так: "заменить все двойные вхождения косой черты на единичные". Из строки знаки мы удалять не можем, но можем удалять из StringBuilder-а, а значит код выше можно превратить в этот:

private static String getSanitizedPath(String path) {  int index = path.indexOf("//");  if (index >= 0) {    StringBuilder sanitized = new StringBuilder(path);    while (index != -1) {      sanitized.deleteCharAt(index);      index = sanitized.indexOf("//", index); //не начинай сначала ;)    }    return sanitized.toString();  }  return path;}

В некоторых случаях использование StringBuilder.deleteCharAt(int) позволяет существенно облегчить понимание кода:

// org.springframework.web.util.UrlPathHelperprivate String removeSemicolonContentInternal(String requestUri) {  int semicolonIndex = requestUri.indexOf(';');  while (semicolonIndex != -1) {    int slashIndex = requestUri.indexOf('/', semicolonIndex);    String start = requestUri.substring(0, semicolonIndex);    requestUri = (slashIndex != -1) ? start + requestUri.substring(slashIndex) : start;    semicolonIndex = requestUri.indexOf(';', semicolonIndex);  }  return requestUri;}

Логика здесь довольно запутанная, но на высоком уровне метод удаляет содержимое, выделенное ; внутри ссылки, превращая строку вроде /foo;f=F;o=O;o=O/bar;b=B;a=A;r=R в /foo/bar;b=B;a=A;r=R.

Можно избавиться от взятия подстроки и склейки переписав метод вот так:

private static String removeSemicolonContentInternal(String requestUri) {  int semicolonIndex = requestUri.indexOf(';');  if (semicolonIndex == -1) {    return requestUri;  }  StringBuilder sb = new StringBuilder(requestUri);  while (semicolonIndex != -1) {    int slashIdx = sb.indexOf("/", semicolonIndex + 1);    if (slashIdx == -1) {      return sb.substring(0, semicolonIndex);    }    sb.delete(semicolonIndex, slashIdx);    semicolonIndex = sb.indexOf(";", semicolonIndex);  }  return sb.toString();}

На первый взгляд, кода стало больше: 12 строк превратились в 16. С другой стороны, он стал выразительнее и проще для понимания, что идёт приятной добавкой к улучшенной производительности.

Все изменения по теме, а также бенчмарк можно увидеть здесь.

Мопед не мой

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

// org.springframework.util.StringUtilspublic static String trimLeadingWhitespace(String str) {  if (!hasLength(str)) {    return str;  }  StringBuilder sb = new StringBuilder(str);  while (sb.length() > 0 && Character.isWhitespace(sb.charAt(0))) {    sb.deleteCharAt(0);  }  return sb.toString();}

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

public static String trimLeadingWhitespace(String str) {  if (!hasLength(str)) {    return str;  }  int idx = 0;  while (idx < str.length() && Character.isWhitespace(str.charAt(idx))) {    idx++;  }  return str.substring(idx);}

Этот код значительно быстрее первоначальной версии, а также потребляет меньше памяти, ведь в худшем случае создаётся только один объект (в лучшем при idx = 0 метод str.substring()вернёт строку, на которой он был вызван).

Данный подход был использован для улучшения нескольких методов, больше подробностей тут.

Мелочь

Если в коде есть что-то вроде

char[] chars;//...return new String(chars, 0, chars.length);

то это всегда можно переписать в виде

char[] chars;//...return new String(chars);

Производительность это сильно не улучшит, однако, перефразируя рекламу моющего средства из 90-х, "если не видно разницы, то зачем писать больше?" :)

Заключение

На этом всё, надеюсь примеры были вам интересны и полезны. Описывайте свои улучшения в комментариях, самые интересные добавлю в статью. До новых встреч!

Подробнее..

Разбиваем строку на подстроки по разделяющим символам своими руками

19.03.2021 16:09:40 | Автор: admin

Введение

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

Вообще говоря, сама задача разбиения строк на подстроки, каждая из которых отделена в исходной строке определённым символом, является довольно распространённой. Очень часто необходимо извлечь из строки слова, разделённые пробелами. Конечно, в стандартной библиотеке языка Си уже есть функция strtok (заголовочный файл <string.h>), но она имеет свои побочные эффекты, перечисленные ниже.

  1. Функция модифицирует исходную строку, разбивая её на лексемы. Она возвращает указатель на саму лексему, или NULL, в случае, когда нет больше лексем. Подробнее о ней можно прочитать здесь.

  2. Так как функция модифицирует строку, то при передачи ей строчного литерала, будет получено SEGV, поскольку память для таких литеральных строк выделяется в сегменте кода, доступного только для чтения.

  3. Для последующих вызовов, функции необходимо передавать нулевой указатель (литерал NULL), чтобы она могла продолжить сканирование с последней распознанной лексемы (предыдущего вызова).

  4. Она не учитывает экранирование символов разделителей.

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

  1. Не менять оригинальную строку, в которой ищутся лексемы.

  2. Для каждой найденной лексемы создавать новую строку.

  3. Сохранять свою текущую позицию, а именно - указатель на подстроку, которая ещё не разбиралась.

  4. Иметь однородную последовательность вызовов.

  5. Иметь возможность экранировать символы разделители, при сложных лексемах.

Основные шаги при разделении строк.

При определении подстрок разделённых между собой каким-либо символом, прежде всего необходимо иметь возможность определять его наличие в строке.

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

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

Разработка функции.

Приступим к разработке. Для начала определим заголовочный файл "str_utils.h", содержащий все прототипы необходимых функций. Реализации функций положим в файл "str_utils.c".

Начнём с функции нахождения символов в строке. Библиотечная функция strchr могла бы решить эту задачу. Но проблема в том, что она не допускает в качестве аргумента строки, в которой надо искать символ, значения NULL. При попытке компилировать с флагами -Wall -Werror, файл с таким аргументом не скомпилируется. Хотя, такую ситуацию можно было бы обработать, вернув NULL. Поэтому был определён свой вариант данной функции с именем contains_symbol. Её прототип выглядит следующим образом:

size_t contains_symbol(char *src, char symbol);

Её реализация определена следующим образом (файл "str_utils.c"):

size_t contains_symbol(char *src, char symbol){  size_t pos = 1;  if(symbols == NULL)    return -1;  while(*symbols != '\0'){    if(*symbols++ == symbol)      return pos;    pos++;  }  return 0;}

Данная функция возвращает позицию символа в строке, увеличенную на единицу. Она не учитывает нулевой символ. Если символ не был найден, функция вернёт 0, либо -1, если ей передали NULL. Её удобно использовать в цикле while, при проверке текущего символа строки на его наличие в другой строке.

Для инкапсуляции работы с памятью был определён отдельный заголовочный файл "mem.h", содержащий следующие прототипы:

void *alloc_mem(size_t nbytes);void *calloc_mem(size_t nelems, size_t elem_size);#define alloc_str(x) ((char *) alloc_mem(x + 1))

Соответствующие функции реализованы в отдельном файле "mem.c":

#include <string.h>#include <stdlib.h>void *alloc_mem(size_t nbytes){  char *buf = (char *)malloc(nbytes);  if(buf != NULL){    memset(buf, '\0', nbytes);    return buf;  }  exit(-1);}void *calloc_mem(size_t nelems, size_t elem_size){  void *buf = calloc(nelems, elem_size);  if(buf != NULL){    return buf;  }  exit(-1);}

Они выделяют блок памяти в куче, содержащий указанное количество байт, а также дополнительно его обнуляют (функция alloc_mem).

Функция обрезки разделителей строки trim_separators выглядит следующим образом:

/* trims symbols from separators at src string *//* returns new trimmed string */char *trim_separators(char *src, char *separators);
char *trim_separators(char *src, char *separators){  if(src == NULL || separators == NULL)    return NULL;  char *sp = src;  while(contains_symbol(separators, *sp)) sp++;    /* if it contains only symbols from separators => NULL */  if(sp - s == strlen(s)) return NULL;    char *sp2 = s + strlen(s) - 1; /* last char at src */  while(contains_symbol(separators, *sp2)) sp2--;    /* if it contains only symbols from separators => NULL */  if(sp2 < s) return NULL;    size_t sz = 0;  if(sp2 - sp == 0 && *sp == '\0') return NULL; /* zero byte is not a character */  else if(sp2 - sp == 0){    sz = 1;  }  else{    sz = (sp2 - sp) + 1;  }  char *res = alloc_mem(sz);  memcpy(res, sp, sz);/* copy all chars except last zero byte */  return res;}

В начале мы проверяем на NULL аргументы функции. Если они нулевые, то возвращаем NULL.

Далее, через указатель sp, проходим строку слева направо, пока мы встречаем символы из строки separators. Если мы прошли всю строку, значит она целиком и полностью состоит из сепараторов, следовательно надо удалить все символы, или же просто вернуть NULL.

char *sp = src;while(contains_symbol(separators, *sp)) sp++;  /* if it contains only symbols from separators => NULL */if(sp - s == strlen(s)) return NULL;

Аналогично, далее через указатель sp2, проходим строку справа налево, проверяя, находится ли текущий символ в массиве separators. Если это не так, то мы прерываем цикл, а указатели будут содержать ссылку на первые символы, не являющимися разделителями. Если мы опять прошли всю строку, значит снова придётся удалять всю строку, следовательно, возвращаем NULL.

char *sp2 = s + strlen(s) - 1; /* last char at src */while(contains_symbol(separators, *sp2)) sp2--;  /* if it contains only symbols from separators => NULL */if(sp2 < s) return NULL;

Наконец, вычисляем длину строки. Если указатели ссылаются на одно и то же место, то в строке был лишь один символ, не являющийся разделителем, а потому размер результата будет равным 1 байту (один лишний байт для нулевого символа учтён в макросе alloc_str). Если же этот единственный символ является нулевым (маркером конца), то возвращаем NULL. Иначе берём разницу между адресами указателями, прибавляем к ней единицу, и получаем длину новой строки. Затем мы просто выделяем память для новой строки и копируем в неё строку, начинающуюся с указателя sp.

Теперь, объединим работу выше написанных функции, в единую функцию get_token().

Код функции get_token дан ниже:

char *get_token(char *src, char *delims, char **next){  if(src == NULL || delims == NULL)    return NULL;  char *delims_p = delims;  /* the end of lexem (points to symbol that follows right after lexem */  char *src_p = trim_separators(src, delims);  /* the begining of the lexem */  char *lex_begin = src_p;  if(src_p == NULL){    *next = NULL;    return NULL;  }    /* flag that indicates reaching of delimeter */  int flag = 0;  while(*src_p != '\0'){    flag = 0;    while(*delims_p != '\0'){      if(*delims_p == *src_p){        flag = 1;        break;      }      delims_p++;    }    if(flag == 1)      break;    delims_p = delims;    src_p++;  }    /* now src_p points to the symbol right after lexem */  /* compute lexem size and reset pointers (from trimmed to the original src) */  char *offset;  size_t tok_size;  offset = (src + strspn(src, delims));  tok_size = (src_p - lex_begin);  free(lex_begin);  lex_begin = offset;  src_p = offset + tok_size;  if(*src_p == '\0')    *next = NULL;  else    *next = src_p;    /* result token */  char *res = alloc_str(tok_size);  memcpy(res, lex_begin, tok_size);  return res;}

В ней используется функция обрезки trim_separators(). Функция обрезки возвращает новую строку, и далее сканирование ведётся по ней. В цикле лишь проверяется, не равен ли текущий символ какому-либо символу разделителю из массива символов delims, и если равен, то выйти из цикла. Указатель src_p проходит по сканируемой строке. После цикла он будет указывать на символ, следующий за лексемой (конец лексемы). А начало лексемы сохраняется в указателе lex_begin, который изначально указывает на начало обрезанной, сканируемой строки. После обнаружения границ лексемы, вычисляется её размер (её число символом), а затем сканируемая строка удаляется из динамической кучи. Затем указатели переустанавливаются на позиции в оригинальной строке (первый аргумент функции get_token()), а часть строки, которая ещё не была разобрана, присваивается в качестве содержимого двойному указателю next. Обратите внимание, что next является ссылкой на другой указатель (в данном случае, на указатель строки). Двойной указатель позволяет менять значение переменной типа char *, записывая новый адрес в next. Для первого вызова данной функции, next должен хранить адрес переменной указателя, которая указывает на строку и хранит адрес первой ячейки строки. Однако, при работе с двойным указателем возможна серьёзная и незаметная ошибка, если в качестве начального значения next передать адрес переменной, которая непосредственно указывает на строку, а не адрес переменной копии, которая содержит копию адреса строки. В следующем разделе подробно описана данная ситуация, и показан пример работы данной функции.

Пример работы get_token().

Ниже дан простой рабочий пример функции get_token(). Оригинальная строка с лексемами хранится в указателе test, копия адреса строки (копия переменной test) хранится в переменной copytest. Указатель tok хранит текущую распознанную лексему, а next - сканируемую часть строки. Данная программа разделяет строку test по пробелу и символу табуляции на подстроки, и выводит их. Также она выводит саму строку test до и после работы функции. Как можно убедиться по выводу, оригинальная строка не меняется.

#include <stdio.h>#include <stdlib.h>#include <string.h>#include "mem.h"#include "str_utils.h"int main(int argc, char **argv){  char *test = "  They have  a    cat.\n \0";  char *copytest = test;  char **next = &copytest; /* has side effect on copytest */  char *tok = NULL;    printf("src:%s\n", test);  printf("copytest:%s\n", copytest);  while(*next != NULL){    tok = get_token(*next, " \t\0", next);    if(tok == NULL)      break;    printf("%s\n", tok);    free(tok);  }  printf("src after:%s\n", test);  printf("copytest after:%s\n", copytest);  return 0;}  

Вывод данной программы:

src:  They have  a    cat.copytest:  They have  a    cat.Theyhaveacat.src after:  They have  a    cat.copytest:(null)

Обратите внимание, что в цикле есть дополнительная проверка на NULL указателя tok. Дело в том, что при получении последнего слова в строке (а именно "cat.\n"), указатель next будет указывать на подстроку, состоящую лишь из одних пробелов (плюс нулевой символ). Функция trim_separators()для таких строк возвращает NULL, так как по логике придётся урезать все символы в строке. В итоге get_token() также вернёт NULL, поскольку уже ничего не осталось для сканирования. Поэтому переменная tok сохранит значение NULL, на последнем шаге.

Теперь снова по поводу двойного указателя next. Как вы могли заметить, в вышеприведённом коде ему передаётся адрес переменной copytest, а не переменной test. Дело в том, что мы можем нечаянно затереть значение переменной test (именно переменной, а не самой строки). Для примера, изменим код следующим образом. Передадим адрес test в указатель next. В итоге мы получим следующий вывод.

src:  They have  a    cat.copytest:  They have  a    cat.Theyhaveacat.src after:(null)copytest:  They have  a    cat.

Как видите, сама строка не меняется, но изменилось значение переменной test. Теперь она содержит NULL, поскольку на последнем шаге, функция присваивает ей соответствующее значение. Отсюда следует, что операции вида:

*next = addr;*next = NULL;

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

Модификация функции get_token(). Экранирование разделителей.

Функция get_token() умеет возвращать новые подстроки (токены) из исходной строки, не меняя её. Однако она совершенно не умеет их экранировать, в случае, когда лексемы представляют собой более сложные объекты. Например, а что если лексема содержит символ, который мы выбрали в качестве разделителя?

Например, вам необходимо выделять значения из формата CSV, где, каждая строка имеет следующий вид:

1233,"John Cenna","Male",4.22,"2004, 2005, 2006",11234,"John Doe","Male",4.24,"2001, 2004, 2007",01235,"Maria Laws","Female",4.23,"2003, 2006, 2008",1

Данные значения формируют следующую таблицу:

Id

Name

Gender

Coefficient

Years

IsActive

1233

John Cenna

Male

4.22

2004, 2005, 2006

yes

1234

John Doe

Male

4.24

2001, 2004, 2007

no

1235

Maira Laws

Female

4.23

2003, 2006, 2008

yes

Заметим, что в данном случае, значения отделяются друг от друга запятой, причём сам разделитель (запятая) не учитывается, когда он находится в кавычках. Это значит, что сам разделитель дополнительно экранирован (escaped) двойными кавычками.

Для таких особых случаев, была определена новая функция get_token_escaped(), которая в качестве дополнительного параметра принимает массив (строку) символов, экранирующих разделители. Символы разделители не должны пересекаться с данным массивом. Т.е. один и тот же символ должен быть либо управляющим, либо разделяющим но не одним и тем же одновременно. Если же это так, то функция будет возвращать NULL. Для контроля начала и конца экранируемой последовательности, была заведена отдельная переменная neflag. Переменная neflag указывает, не является ли текущий символ частью экранируемой последовательности (neflag => not escaped flag). Она равна 0, когда символ должен быть экранируем, и 1, когда символ не экранируется. В цикле сканирования, сначала текущий символ ищется среди экранирующих (escaped). Если он найден и он равен предыдущему управляющему символу, то устанавливаем соответствующий флаг neflag равным 0, так как была найдена пара - начала и конец экранируемой последовательности. Если же это другой экранирующий символ, не равный предыдущему, то если мы уже находимся в экранируемой последовательности, то ничего не надо делать (продолжаем поиск, в надежде, что мы отыщем нужную пару (пред. символ)). Иначе, если мы нашли его впервые, то запоминаем его в переменной esym, и сбрасываем флаг neflag в 0. Символ разделитель будет учтён, если он был обнаружен (flag == 1) и он не является частью экранируемой последовательности (neflag == 1).

Ниже дан код данной процедуры.

char *get_token_escaped(char *src, char *delims, char *escaped, char **next){  if(src == NULL || delims == NULL || escaped == NULL)    return NULL;  char *delims_p = delims;  char *escaped_p = escaped;  /* the end of lexem (points to symbol that follows right after lexem */  char *src_p = trim_separators(src, delims);  /* the begining of the lexem */  char *lex_begin = src_p;  if(src_p == NULL){    *next = NULL;    return NULL;  }    /* check that (delims INTERSECTION escaped) IS NULL. */  /* IF NOT => return NULL */  int err = 0;  while(*delims_p != '\0'){    while(*escaped_p != '\0' && (err = (*escaped_p == *delims_p) ) != 1) escaped_p++;    escaped_p = escaped;    if(err){      return NULL;    }    delims_p++;  }  delims_p = delims;    /* flag that indicates reaching of delimeter */  int flag = 0;  /* flag that indicates that we are not in escaped sequence */  int neflag = 1;  /* previously saved escape character (i.e. the begining of the escaped seq.) */  char *esym = (char)0;  while(*src_p != '\0'){    flag = 0;    while(*escaped_p != '\0'){      if(*src_p == *escaped_p && *src_p == esym){        neflag = 1;        esym = (char)0;        break;      }      else if(*src_p == *escaped_p && neflag){        neflag = 0;        esym = *escaped_p;        break;      }      escaped_p++;    }    while(*delims_p != '\0'){      if(*delims_p == *src_p){        flag = 1;        break;      }      delims_p++;    }    if(flag && neflag)      break;    delims_p = delims;    escaped_p = escaped;    src_p++;  }    /* now src_p points to the symbol right after lexem */  /* compute lexem size and reset pointers (from trimmed to the original src) */  char *offset;  size_t tok_size;  offset = (src + strspn(src, delims));  tok_size = (src_p - lex_begin);  free(lex_begin);  lex_begin = offset;  src_p = offset + tok_size;  if(*src_p == '\0')    *next = NULL;  else    *next = src_p;    /* result token */  char *res = alloc_str(tok_size);  memcpy(res, lex_begin, tok_size);  return res;}

Пример её использования дан ниже:

#include <stdio.h>#include <stdlib.h>#include <string.h>#include "mem.h"#include "str_utils.h"int main(int argc, char **argv){  char *test = "  They have  \"cats dogs mice  \"\n \0";  char *copytest = test;  char **next = &copytest; /* has side effect on copytest */  char *tok = NULL;    printf("src:%s\n", test);  printf("copytest:%s\n", copytest);  while(*next != NULL){    tok = get_token_escaped(*next, " \t\0", "\"\0", next);    if(tok == NULL)      break;    printf("%s\n", tok);    free(tok);  }  printf("src after:%s\n", test);  printf("copytest after:%s\n", copytest);  return 0;}

Вывод:

src:  They have  "cats dogs mice  "copytest:  They have  "cats dogs mice  "Theyhave"cats dogs mice  "src after:  They have  "cats dogs mice  "copytest after:(null)

Заключение

Разработанная функция get_token() позволяет извлекать лексемы в отдельные новые строки. Она не меняет исходной строки, и имеет одинаковую последовательность вызовов. Из недостатков, она использует двойной указатель для сохранения текущей позиции сканера. Чтобы не затирать значение переменной, адрес которой содержит двойной указатель next, необходимо передавать адрес другой переменной, являющейся копией исходной (см. код выше). Функция также не умет экранировать символы разделители. Эту работу делает другая функция - get_token_escaped().

Функцию get_token_escaped() можно использовать при работе с CSV файлами. Однако ей должны передаваться непересекающиеся множества символов разделителей, и экранирующих символов. Иначе будет неоднозначность между ними. Функция не умеет пока анализировать такие неоднозначности, поэтому в таких случаях она вернёт NULL. Кроме того, она не допускает вложенных экранируемых последовательностей. Т.е. если был встречен экранируемый символ, всё что следует за ним, включительно до его клона (такого же символа, но в следующей позиции), считается как одна экранируемая последовательность.

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

Подробнее..

Ах, эти строки

13.08.2020 12:11:08 | Автор: admin

Это текстовая версия моего доклада "Ах, эти строки" на конференции JPoint-2020.
Дабы не тратить время читателей зря, сразу расставим все точки над "ё".


О чём статья?


Статья об эффективном (или не очень) использовании строк.


Для кого статья?


Статья для разработчиков, занимающихся производительностью, и им сочувствующих.


Откуда всё это?


Что-то выловлено в коде проекта, что-то во фреймворках и библиотеках.


Что, чем и на чём измеряли?


  • код бенчмарков и результаты прогонов доступны на ГитХабе
  • для измерения использовался JMH 1.23
  • замеры проводились на рабочей машине с Intel Core i7-7700 (сами по себе цифры не важны, важны соотношения между ними и выявленные закономерности)
  • по умолчанию использовался JDK 11, но также 8 и 14 (явно прописаны на соответствующих страницах)
  • режим бенчмарков: среднее время выполнения + расход памяти (меньше значит лучше)

Пакет java.lang и его обитатели


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


Но есть класс неподвластный консерватизму: java.lang.String. Ниже список последних предложений по его улучшению (или улучшению работы с ним), многие из них уже реализованы:


  • JEP 192: String Deduplication in G1
  • JEP 250: Store Interned Strings in CDS Archives
  • JEP 254: Compact Strings
  • JEP 280: IndifyString Concatenation
  • JEP 326: Raw String Literals (Preview)
  • JEP 355: Text Blocks (Preview)
  • JEP 348: Compiler Intrinsics for Java SE APIs (в основном это пока про String.format())

Обратите внимание на сжатые строки они затрагивают основы основ если сравнить содержимое java.lang.String в "восьмёрке" и в "девятке", то изменилось решительно всё.


Почему именно строки


Повышенное внимание разработчиков платформы к строкам тоже понятно и подробно изложено в классическом докладе Катехизис java.lang.String. Вкратце:


  • они [строки] везде
  • они съедают весомую часть кучи
  • они [при неправильном использовании] могут ухудшить производительность
  • когда им хорошо, то хорошо всем

Подходы к прокачиванию производительности


Когда мы улучшаем производительность, то становимся перед выбором:


  • наращивать объём исполняемого
  • уменьшать / переупорядочивать объём исполняемого

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


Поскольку большинство из нас это рядовые разработчики и влезть в плюсовый адъ внутри ВМ и сделать там что-то осмысленное могут не только лишь все (мало кто может это сделать), то для нас более перспективным является второй подход делать меньше получая больше. О нём и поговорим.


Основная проблема строк


Проистекает она из JLS 15.18.1 и означает, что [почти] любое преобразование строки порождает новую строку, поэтому зачастую для получения прироста нужно лишь избавиться от ненужных преобразований, при чём многие из них легко формализуются и обращаются в правила статического анализатора.


Отсюда плавно вытекает стратегия и тактика улучшения работы со строками:


  • стратегия: не использовать строки там, где это возможно
  • тактика: по возможности избегать преобразования строк

Ключи и словари


Строки очень часто используются в качестве ключей (внезапно). Причиной является набор уникальных свойств, доступный прямо из коробки:


  • строки неизменяемы
  • строки определяют equals() / hashCode()
  • строки кэшируют хэш-код
  • строки сериализуемы и реализуют java.lang.Comparable (их можно класть в TreeMap)
  • строки особо реализуют Object.equals()
  • любой объект можно представить в виде строки вызвав obj.toString()

Многие знают, что набор постоянных строк-ключей можно представить в виде перечисления, что даёт возможность отказаться от HashMap в пользу EnumMap:


Map<String, ?> map = new HashMap<>();class Constants {  static final String MarginLeft = "margl";  static final String MarginRight = "margr";  static final String MarginTop = "margt";  static final String MarginBottom = "margb";}

легко заменяется на


Map<String, ?> map = new EnumMap<>(Constants.class);enum Constants {  MarginLeft,  MarginRight,  MarginTop,  MarginBottom}

что даёт более легковесный и быстрый словарь:


@Benchmarkpublic Object hm() {  var map = new HashMap<>();  map.put(Constants.MarginLeft, 1);  map.put(Constants.MarginRight, 2);  map.put(Constants.MarginTop, 3);  map.put(Constants.MarginBottom, 4);  return map;}@Benchmarkpublic Object em() {  var map = new EnumMap<>(ConstantsEnum.class);  map.put(ConstantsEnum.MarginLeft, 1);  map.put(ConstantsEnum.MarginRight, 2);  map.put(ConstantsEnum.MarginTop, 3);  map.put(ConstantsEnum.MarginBottom, 4);  return map;}

Прирост ощутим:


                               Mode    Score    Error   UnitsenumMap                        avgt   23.487   0.694   ns/ophashMap                        avgt   67.480   2.395   ns/openumMap:gc.alloc.rate.norm    avgt   72.000   0.001    B/ophashMap:gc.alloc.rate.norm    avgt  256.000   0.001    B/op

Перебор также пойдёт бодрее:


@Benchmarkpublic void hashMap(Data data, Blackhole bh) {  Map<String, Integer> map = data.hashMap;  for (String key : data.hashMapKeySet) {    bh.consume(map.get(key));  }}@Benchmarkpublic void enumMap(Data data, Blackhole bh) {  Map<ConstantsEnum, Integer> map = data.enumMap;  for (ConstantsEnum key : data.enumMapKeySet) {    bh.consume(map.get(key));  }}

что даёт


                               Mode    Score    Error   UnitsenumMap                        avgt   36.397   3.080   ns/ophashMap                        avgt   55.652   4.375   ns/op

В сложных случаях так не получается:


// org.springframework.aop.framework.CglibAopProxyMap<String, Integer> map = new HashMap<>();getCallbacks(Class<?> rootClass) {  Method[] methods = rootClass.getMethods();  for (intx = 0; x < methods.length; x++) {    map.put(methods[x].toString(), x);          // <------  }}// зеркальный методaccept(Method method) {  String key = method.toString();  // key используется тут в качестве ключа}

Проблема понятна: вызов java.lang.reflect.Method.toString() порождает новую строку. Много ли теряем?


@State(Scope.Thread)@BenchmarkMode(Mode.AverageTime)@OutputTimeUnit(TimeUnit.NANOSECONDS)public class MethodToStringBenchmark {  private Method method;  @Setup  public void setup() throws Exception {    method = getClass().getMethod("toString");  }  @Benchmark  public String methodToString() { return method.toString(); }}

Это простейший случай вызов method.toString() возвращает строку:


"public java.lang.String java.lang.Object.toString()"

а стоит это удовольствие немало:


                                       Mode  Score  Error   UnitsmethodToString                         avgt   85,4   1,3   ns/opmethodToString:gc.alloc.rate.norm     avgt  344,0   0,0    B/op

Если мы провернём это в более жизненном ключе, например:


public class MethodToStringBenchmark {  private Method method;  @Setup  public void setup() throws Exception {    method = getClass().getMethod("getInstance");  }  @Benchmark  public String methodToString() { return method.toString(); }  MethodToStringBenchmark getInstance() throws ArrayIndexOutOfBoundsException {    return null;  }}

то расценки существенно вырастут:


                                       Mode     Score    Error   UnitsmethodToString                         avgt   199.765   3.807   ns/opmethodToString:gc.alloc.rate.norm     avgt  1126.400   9.817    B/op

ведь возвращается уже более внушительная строка:


"public tsypanov.strings.reflection.MethodToStringBenchmark tsypanov.strings.reflection.MethodToStringBenchmark.getInstance() throws java.lang.ArrayIndexOutOfBoundsException"

На первый взгляд всё безнадёжно, ведь никаких enum-ов не напасёшься на все проксируемые методы. Давайте лучше присмотримся к самому классу java.lang.reflect.Method. Уже поверхностный осмотр показывает, что он вполне может быть ключом вместо строки:


  • реализует equals() / hashCode()
  • неизменяемый *

Почему неизменяемый со звёздочкой?


не торопитесь открывать, подумайте

Всё из-за него:


public final class Method extends Executable {  @Override  @CallerSensitive  public void setAccessible(boolean flag) {      AccessibleObject.checkPermission();      if (flag) checkCanSetAccessible(Reflection.getCallerClass());      setAccessible0(flag);  }}

Это тот самый случай, когда теория запрещает использовать объект этого класса в качестве ключа, ведь у него есть изменяющий состояние метод, а крестьянская смекалка говорит "Можно!". Ведь сколько бы мы ни дёргали за ручку Method.setAccessible() поведение его equals()/hashCode() не изменится.


Есть и недостатки:


  • java.lang.reflect.Method не реализует Comparable
  • хэш-код объекта Method не равен хэш-коду строки (и он не кэшируется)

В данном случае нам важно только положить пару "ключ-значение" в словарь и получить значение по ключу, следовательно меняем String на Method.


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


@Configurationpublic class AspectConfig {  @Bean  ServiceAspect serviceAspect() { return new ServiceAspect(); }  @Bean  @Scope(BeanDefinition.SCOPE_PROTOTYPE)  AspectedService aspectedService() { return new AspectedServiceImpl(); }  @Bean  AbstractAutoProxyCreator proxyCreator() {    var factory = new AnnotationAwareAspectJAutoProxyCreator();    factory.setProxyTargetClass(true);    factory.setFrozen(true);           // <--- обратите внимание    return factory;  }}

Небольшое пояснение: у нас есть некий компонент-прототип (это нужно, чтобы хранить состояние) с 1 методом, обёрнутым в 1 аспект. Поскольку в нашем случае мы знаем, что цепочка проброса неизменна, то её можно "заморозить", что позволяет "Спрингу" выполнить под капотом некоторые оптимизации (см. документацию).


Вычислим стоимость создания этого бина:


@State(Scope.Thread)@BenchmarkMode(Mode.AverageTime)@OutputTimeUnit(TimeUnit.MICROSECONDS)public class AspectPrototypeBenchmark {  private AnnotationConfigApplicationContext context;  @Setup  public void setUp() {    context = new AnnotationConfigApplicationContext(AspectConfig.class);  }  @Benchmark  public AspectedService getAdvisedBean() {    return context.getBean(AspectedService.class);  }  @TearDown  public void closeContext() { context.close(); }}

Имеем:


                                       Mode      Score     Error   UnitsbeforegetAdvisedBean                         avgt     14.024    0.164   us/opgetAdvisedBean:gc.alloc.rate.norm     avgt  10983.307   14.193    B/opaftergetAdvisedBean                         avgt      8.150    0.202   us/opgetAdvisedBean:gc.alloc.rate.norm     avgt   7133.664    5.594    B/op

Неплохо, как для такого простого изменения.


З.. Обратите внимание, что этот бенчмарк лежит в другом репозитории, где собраны бенчмарки для "Спринга".


Составные ключи


В JDK есть класс ObjectStreamClass, использующийся при сериализации, в нём вложенный класс FieldReflectorKey, а там внутри проблема.


public class ObjectStreamClass implements Serializable {  private static class Caches {    static final ConcurrentMap<FieldReflectorKey, Reference<?>> reflectors =            new ConcurrentHashMap<>();  }  private static class FieldReflectorKey extends WeakReference<Class<?>> {    private final String sigs;    private final int hash;    private final boolean nullClass;    // ...}

Фамилия имя и отчество виновного известны: JDK-6996807 FieldReflectorKey hash code computation can be improved. Уже из заголовка понятно: вычисление хэш-кода стоит неоправданно дорого. Больное место находится в конструкторе:


FieldReflectorKey(Class<?> cl, ObjectStreamField[] fields,                    ReferenceQueue<Class<?>> queue){  super(cl, queue);  nullClass = (cl == null);  StringBuilder sbuf = new StringBuilder();  // <---- !!!  for (int i = 0; i < fields.length; i++) {    ObjectStreamField f = fields[i];    sbuf.append(f.getName()).append(f.getSignature());  }  sigs = sbuf.toString();  hash = System.identityHashCode(cl) + sigs.hashCode();}

После внесения изменений получаем:


FieldReflectorKey(Class<?> cl, ObjectStreamField[] fields,                  ReferenceQueue<Class<?>> queue){  super(cl, queue);  nullClass = (cl == null);  sigs = new String[2 * fields.length];  for (int i = 0, j = 0; i < fields.length; i++) {    ObjectStreamField f = fields[i];    sigs[j++] = f.getName();    sigs[j++] = f.getSignature();  }  hash = System.identityHashCode(cl) + Arrays.hashCode(sigs);}

Теперь вместо цельной строки создаётся массив, заполняемый именами и сигнатурами классов, что даёт небольшой прирост:


SPECjvm2008:serial improves a little bit with this patch, and the allocation rate is down ~5%.

Ровно та же проблема была выловлена в "Спринге" в o.s.context.support.StaticMessageSource:


public class StaticMessageSource extends AbstractMessageSource {  private final Map<String, String> messages = new HashMap<>();  @Override  protected String resolveCodeWithoutArguments(String code, Locale locale) {    return this.messages.get(code + '_' + locale.toString());  }  public void addMessage(String code, Locale locale, String msg) {    // ...    this.messages.put(code + '_' + locale.toString(), msg);  }}

Измерить производительность можно с помощью бенчмарка:


private final String code = "code1";private final Locale locale = Locale.getDefault();@Benchmarkpublic Object concatenation(Data data) {  return data.stringObjectMap.get(data.code + '_' + data.locale);}

Что даёт


concatenation                          avgt     53.241    1.494   ns/opconcatenation:gc.alloc.rate.norm      avgt    120.000    0.001    B/op

Решение составной ключ, который может быть представлен в виде отдельного класса


@EqualsHashCode@RequiredArgsConstructorprivate static final class Key {  private final String code;  private final Locale locale;}

списка:


Arrays.asList(code, locale);// или в старших JDKList.of(code, locale)

или даже записи (если вы красавчик и у вас Java 14)


private static record KeyRec(String code, Locale locale) {}

Рассмотрим их показатели:


                                       Mode      Score     Error   UnitscompositeKey                           avgt      6.065    0.415   ns/opconcatenation                          avgt     53.241    1.494   ns/oplist                                   avgt     31.001    1.621   ns/opcompositeKey:gc.alloc.rate.norm       avgt      10              B/opconcatenation:gc.alloc.rate.norm      avgt    120.000    0.001    B/oplist:gc.alloc.rate.norm               avgt     80.000    0.001    B/op

Обратите внимание, что на создание 1 составного ключа мы выделили 0 байт, т. е. анализ области видимости отработал на отлично (чего не скажешь о списке), поэтому я предложил именно такой вариант. Однако Ёрген Холлер, занимавшийся этим изменением рассудил иначе. На первый взгляд, решение несколько странное, ведь последовательный поиск в двух словарях очевидно дороже:


                                       Mode      Score     Error   UnitscompositeKey                           avgt      6.065    0.415   ns/opmapInMap                               avgt      9.330    1.010   ns/opmapInMap:gc.alloc.rate.norm           avgt      10              B/opcompositeKey:gc.alloc.rate.norm       avgt      10              B/op

Но дороже он будет только при действенном анализе области видимости, а с этим иногда напряжёнка:


этот же бенчмарк на JDK 14                                       Mode      Score     Error   UnitscompositeKey                           avgt      7.803    0.647   ns/opmapInMap                               avgt      9.330    1.010   ns/oprecord                                 avgt     13.240    0.691   ns/oplist                                   avgt     37.316    6.355   ns/opconcatenation                          avgt     69.781    7.604   ns/opcompositeKey:gc.alloc.rate.norm       avgt     24.001    0.001    B/opmapInMap:gc.alloc.rate.norm           avgt      10              B/oprecord:gc.alloc.rate.norm             avgt     24.001    0.001    B/oplist:gc.alloc.rate.norm               avgt    105.602    9.786    B/opconcatenation:gc.alloc.rate.norm      avgt    144.004    0.001    B/op

Оп-па! А ключ-то составной теперь создаётся в куче! Мораль сей басни такова: скаляризация и анализ области видимости очень хрупкие вещи, которые не прописаны в спецификации языка и ВМ, и которые нам никто не обещает.


Вывод для разработчика простой: склейка строк для создания ключа это плохо, ибо


  • требует относительно много времени и доппамяти
  • при частом обращении может стать узким местом

Выход есть отдельный класс для составного ключа (в крайнем случае подойдёт массив или Arrays.asList() / List.of()).


Склеивание строк


Когда речь заходит о склейке мы часто задаём неправильный вопрос: какой способ самый лучший? Правильный вопрос, ПМСМ, звучит так: а нужно ли вообще их клеить? Для примера рассмотрим часть метода org.springframework.core.ResolvableType.toString():


StringBuilder result = new StringBuilder(this.resolved.getName());if (hasGenerics()) {  result.append('<');  result.append(StringUtils.arrayToDelimitedString(getGenerics(), ", "));  result.append('>');}return result.toString();

Переберём все возможные исполнения, благо их аж целых 2:
1) hasGenerics() возвращается истину и мы честно клеим строки
2) hasGenerics() возвращается ложь и мы переливаем значение this.resolved.getName() в StringBuilder, а оттуда снова в строку


Очевидно, что во втором случае (он наиболее частый, т. к. большинство бинов нетипизированы) на выходе мы получим ту же строку, что и из this.resolved.getName(), поэтому код можно упростить, повысив одновременно его производительность:


if (hasGenerics()) {  return this.resolved.getName()     + '<'    + StringUtils.arrayToDelimitedString(getGenerics(), ", ")    + '>';}return this.resolved.getName();

Обратите внимание: после внесения StringBuilder-а внутрь условного блока мы можем отказаться от него в пользу + (об этом чуть ниже).


Склейка: если всё-таки нужно


Рассмотрим задачу преобразования массива байт в шестнадцатеричный вид. Решение следующее:


private static String bytesToHexString(byte[] bytes) {  StringBuilder sb = new StringBuilder();  for (int i = 0; i < bytes.length; i++) {    sb.append(Integer.toString((bytes[i] & 0xff) + 0x100, 16).substring(1));  }  return sb.toString();}

Вопиющая неэффективность метода bytesToHexString очевидна даже новичку: преобразование байта в строку, взятие подстроки, добавление в StringBuilder. На этом варианте останавливаться не будем (хотя он и был выловлен в коде двух проектов). Существует похожий (и тоже неэффективный) вариант решения задачи (взят из статьи про p6spy):


public String toHexString(byte[] bytes) {  StringBuilder sb = new StringBuilder();  for (byte b : bytes) {    int temp = (int) b & 0xFF;    sb.append(HEX_CHARS[temp / 16]);    sb.append(HEX_CHARS[temp % 16]);  }  return sb.toString();}

При первом же рассмотрении разработчик наверняка обратит внимание на создание StringBuilder-а конструктором по умолчанию, хотя нам известно количество проходов по циклу, а также тот факт, что при каждом проходе добавляются два знака шестнадцатеричного алфавита. Вырисовывается очевидное улучшение:


public String toHexStringPatched(byte[] bytes) {  StringBuilder sb = new StringBuilder(bytes.length * 2);  for (byte b : bytes) {    int temp = (int) b & 0xFF;    sb.append(HEX_CHARS[temp / 16]);    sb.append(HEX_CHARS[temp % 16]);  }  return sb.toString();}

Если мы прогоним через оба метода 1 Мб данных, то обнаружим, что второй даёт существенную экономию памяти при незначительном приросте по времени:


original                          avgt        4167,950      82,704   us/oppatched                           avgt        3972,118      34,817   us/oporiginal:gc.alloc.rate.norm      avgt    13631776,184       0,005    B/oppatched:gc.alloc.rate.norm       avgt     8388664,173       0,002    B/op

Оказывается, что львиную долю занимает проверка выхода за пределы массива и доступ к самому массиву:


@Overridepublic AbstractStringBuilder append(char c) {  ensureCapacityInternal(count + 1);  value[count++] = c;  return this;}

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


public String toHexString(byte[] bytes) {  char[] result = new char[bytes.length * 2];  int idx = 0;  for (byte b : bytes) {    int temp = (int) b & 0xFF;    result[idx++] = HEX_CHARS[temp / 16];    result[idx++] = HEX_CHARS[temp % 16];  }  return new String(result);}

И вот теперь мы получим существенный прирост:


original                          avgt        4167,950      82,704   us/oppatched                           avgt        3972,118      34,817   us/opchars                             avgt        1377,829       4,861   us/oporiginal:gc.alloc.rate.norm      avgt    13631776,184       0,005    B/oppatched:gc.alloc.rate.norm       avgt     8388664,173       0,002    B/opchars:gc.alloc.rate.norm         avgt     6291512,057       0,001    B/op

Любопытно, что если запустить этот же код на старших версиях JDK, то неожиданно возникает просадка по памяти:


original                          avgt        3813,358      75,014   us/oppatched                           avgt        3733,343      90,589   us/opchars                             avgt        1377,829       4,861   us/oporiginal:gc.alloc.rate.norm      avgt     6816056,159       0,005    B/oppatched:gc.alloc.rate.norm       avgt     4194360,157       0,006    B/opchars:gc.alloc.rate.norm         avgt     6291512,057       0,001    B/op   <----

Совершенно не очевидно для нас показатель потребления памяти для массива вернулся на прежний уровень. Причина в реализации работы со сжатыми строками:


abstract class AbstractStringBuilder implements Appendable, CharSequence {  byte[] value;  public AbstractStringBuilder append(char c) {    this.ensureCapacityInternal(this.count + 1);    if (this.isLatin1() && StringLatin1.canEncode(c)) {      this.value[this.count++] = (byte)c;                     // <-----    } else {      // ...    }    return this;  }}

Если на вход StringBuilder.append(char) пришел знак, входящий в множество ASCII (а шестнадцатеричный алфавит входит туда по умолчанию), то его старший байт усекается, а младший кладётся в хранилище. Если же используется голый массив, то в него всегда кладётся полновесный char о двух байтах. Поэтому если у вас на проекте JDK 9 и выше, то шестнадцатеричный алфавит нужно объявлять как массив байт, а char[] менять на byte[].


Вывод для разработчика: иногда склейка строк сводится к задаче о буферизации с известными узкими местами:


  • проверкой выхода за пределы хранилища
  • расширением хранилища
  • переносом данных при расширении

Универсальное решение: семь раз отмерь один раз отрежь.


Необходимо отметить, что выше описан редкий случай известно количество проходов и объём данных, записываемых на каждом проходе. Обычно же имеем дело со следующими разновидностями:


// сложение String str = s1 + s2 + s3;// склеивание цепочкойString str = new StringBuilder().append(str1).append(str2).append(str3).toString();// склеивание путём раздельного добавленияStringBuilder sb = new StringBuilder();sb.append(str1);sb.append(str2);sb.append(str3);String str = sb.toString();

Измерим производительность с помощью бенчмарка:


private final String str1 = "1".repeat(10);private final String str2 = "2".repeat(10);private final String str3 = "3".repeat(10);private final String str4 = "4".repeat(10);private final String str5 = "5".repeat(10);@Benchmark public String concatenation() { /*...*/ }@Benchmark public String chainedAppend() { /*...*/ }@Benchmark public String newLineAppend() { /*...*/ }

Ожидаемо побеждает сложение, в затылок ему дышит склеивание цепочкой:


                                    Mode     Score     Error   UnitschainedAppend                       avgt    33,973    0,974   ns/opconcatenation                       avgt    36,189    1,260   ns/opnewLineAppend                       avgt    71,083    5,180   ns/opchainedAppend:gc.alloc.rate.norm   avgt    96,000    0,001    B/opconcatenation:gc.alloc.rate.norm   avgt    96,000    0,001    B/opnewLineAppend:gc.alloc.rate.norm   avgt   272,000    0,001    B/op

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


StringBuilder sb = new StringBuilder()        .append(str1)        .append(str2)        .append(str3);if (smth) sb.append(str4);return sb.append(str5).toString();

Ухудшится ли производительность и если да, то будет ли она зависеть от точки разрыва? Оказывается, что одного единственного разрыва достаточно для слома интринзификации, а без неё мы откатываемся к раздельному добавлению:


                                    Mode     Score     Error   UnitschainedAppend                       avgt    33,973    0,974   ns/opconcatenation                       avgt    36,189    1,260   ns/opnewLineAppend                       avgt    71,083    5,180   ns/optornAppend                          avgt    66,261    2,095   ns/opchainedAppend:gc.alloc.rate.norm   avgt    96,000    0,001    B/opconcatenation:gc.alloc.rate.norm   avgt    96,000    0,001    B/opnewLineAppend:gc.alloc.rate.norm   avgt   272,000    0,001    B/optornAppend:gc.alloc.rate.norm      avgt   272,000    0,001    B/op

Это подводит нас уже к менее очевидному выводу: сшивание цепочки даёт конские приросты и позволяет упростить код (вспомните пример с ResolvableType.toString()). Рассмотрим часть встроенного в "Спринг" профилировщика:


// o.s.a.interceptor.AbstractMonitoringInterceptorString createInvocationTraceName(MethodInvocation invocation) {  StringBuilder sb = new StringBuilder(getPrefix());                    // < ----  Method method = invocation.getMethod();  Class<?> clazz = method.getDeclaringClass();  if (logTargetClassInvocation && clazz.isInstance(invocation.getThis())) {    clazz = invocation.getThis().getClass();  }  sb.append(clazz.getName());  sb.append('.').append(method.getName());  sb.append(getSuffix());  return sb.toString();}

Обратите внимание: между объявлением переменной sb и её использованием находится другой код, а значит объявление можно сместить:


String createInvocationTraceName(MethodInvocation invocation) {  Method method = invocation.getMethod();  Class<?> clazz = method.getDeclaringClass();  if (logTargetClassInvocation && clazz.isInstance(invocation.getThis())) {    clazz = invocation.getThis().getClass();  }  StringBuilder sb = new StringBuilder(getPrefix());                    // < ----  sb.append(clazz.getName());  sb.append('.').append(method.getName());  sb.append(getSuffix());  return sb.toString();}

Тут же "Идея" поможет нам всё это ужать и сделать совсем красиво:


protected String createInvocationTraceName(MethodInvocation invocation) {  Method method = invocation.getMethod();  Class<?> clazz = method.getDeclaringClass();  if (logTargetClassInvocation && clazz.isInstance(invocation.getThis())) {    clazz = invocation.getThis().getClass();  }  return getPrefix() + clazz.getName() + '.' + method.getName() + getSuffix();}

Этот код не только проще и выразительнее, но и должен быть производительнее. Проверим:


Гладко вписано в бумаги, да забыли про овраги...
                                Mode      Score     Error   Unitsbefore                          avgt     97,273    0,974   ns/opafter                           avgt     89,089    1,260   ns/opbefore:gc.alloc.rate.norm      avgt    728,000    0,001    B/opafter:gc.alloc.rate.norm       avgt    728,000    0,001    B/op

Ёлки-палки, нормально же общались! Буквально пол-страницы назад в похожем как две капли воды коде ровно такой же финт ушами давал хороший прирост, а тут что-то пошло нет так. Чтобы разобраться давайте выведем наименьший пример, на котором проблема воспроизведётся:


@BenchmarkMode(Mode.AverageTime)@OutputTimeUnit(TimeUnit.NANOSECONDS)@Fork(jvmArgsAppend = {"-Xms2g", "-Xmx2g", "-XX:+UseParallelGC"})public class BrokenConcatenationBenchmark {  @Benchmark  public String slow(Data data) {    Class<? extends Data> clazz = data.clazz;    return "class " + clazz.getName();  }  @Benchmark  public String fast(Data data) {    Class<? extends Data> clazz = data.clazz;    String clazzName = clazz.getName();    return "class " + clazzName;  }  @State(Scope.Thread)  public static class Data {    Class<? extends Data> clazz = getClass();    @Setup    // explicitly load name via Class.getName0()    public void setup() { clazz.getName(); }          <---- обратите внимание  }}

Внешне этот пример очень похож на JDK-8043677. Теперь метод Class.getName():


public String getName() {  String name = this.name;  if (name == null) {    this.name = name = this.getName0();  }  return name;}private native String getName0();

Это обычный ленивый геттер: при первом обращении полю присваивается значение, дальше оно только возвращается. Теперь вспомним, что мы явно вызываем этот метод в setup(), иными словами во время прогона никаких сторонних эффектов уже быть не может. Тем не менее, просадка по производительности стабильно воспроизводится.
Признаюсь, я не нашел объяснения самостоятельно, поэтому задал вопрос на StackOverflow. На выручку пришел apangin, за что ему огромная благодарность. Дело тут вот в чём:


Виртуальная машина собирает статистику исполнения байт-кода. Если один и тот же код исполняется в разных контекстах, то итоговый профиль объединяет в себе статистику по каждому из них. Это называется отравление профиля.
Очевидно, что Class.getName() вызывается не только из кода бенчмарка. И ещё до того, как JIT начинает компиляцию бенчмарка, он уже знает, что условие
if (name == null) {this.name = name = getName0();}


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

По ссылке есть пример достижения ровно такого же эффекта без использования нативного метода. В нашем случае нужно извлечь выражение Class.getName() в отдельную переменную.


И вот теперь у нас есть желаемый прирост:


                                Mode      Score     Error   Unitsbefore                          avgt     97,273    0,974   ns/opafter                           avgt     13,301    0,411   ns/opbefore:gc.alloc.rate.norm      avgt    728,000    0,001    B/opafter:gc.alloc.rate.norm       avgt    280,000    0,001    B/op

Выводы для разработчика:


  • сшивание цепочки = упрощение кода + производительность
  • с старых изданиях JDK (<9) держи в уме угловые случаи

Склейка: среди if-ов как среди рифов


Наш следующий гость библиотека ASM, использующаяся для работы с байт-кодом. Рассмотрим один из методов класса org.objectweb.asm.Type:


void appendDescriptor(final Class<?> clazz, final StringBuilder sb) {  String name = clazz.getName();  for (int i = 0; i < name.length(); ++i) {    char car = name.charAt(i);    sb.append(car == '.' ? '/' : car);  }  sb.append(';');}

Имеем уже описанную выше проблему: данные складываются в хранилище познаково, что медленно, т. к. каждый StringBuilder.append(char) означает отдельную проверку выхода за пределы массива и доступ к нему. Чтобы обратить это в массовое добавление, нужно выразить алгоритм одним словом. И это слово замена, ведь точка заменяется косой чертой, а все прочие знаки остаются без изменений. Значит мы можем переписать код так:


void appendDescriptor(final Class<?> clazz, final StringBuilder sb) {  sb.append(clazz.getName().replace('.', '/'));}

Теперь нужно проверить: выиграем или нет. Ведь у изменённого варианта есть недостаток: при одном единственном вхождении искомого знака String.replace(char, char) создаёт новую строку, что требует времени и доппамяти (чего не наблюдалось в прежнем издании).
Прогоним бенчмарк для класса java.lang.String:


@State(Scope.Thread)@OutputTimeUnit(TimeUnit.NANOSECONDS)@BenchmarkMode(value = Mode.AverageTime)@Fork(jvmArgsAppend = {"-Xms2g", "-Xmx2g"})public class CharacterReplaceBenchmark {  private final Class<?> klass = String.class;  @Benchmark  public StringBuilder manualReplace() {    return ineffective(klass, new StringBuilder());  }  @Benchmark  public StringBuilder stringReplace() {    return effective(klass, new StringBuilder());  }}

Итог неоднозначен:


                                     Mode     Score     Error   UnitsmanualReplace                        avgt    43,312    1,767   ns/opstringReplace                        avgt    30,741    3,247   ns/opmanualReplace:gc.alloc.rate.norm    avgt    56,000    0,001    B/opstringReplace:gc.alloc.rate.norm    avgt   112,000    0,001    B/op

С одной стороны имеем существенный выигрыш по времени, с другой двукратную просадку по памяти. Если вместо java.lang.String полю klass присвоить значение


private final Class<?> klass = CharacterReplaceBenchmark.class;

то результат снова удивит:


                                     Mode     Score     Error   UnitsmanualReplace                        avgt   160,336    2,628   ns/opstringReplace                        avgt    67,258    1,535   ns/opmanualReplace:gc.alloc.rate.norm    avgt   200,000    0,001    B/opstringReplace:gc.alloc.rate.norm    avgt   240,000    0,001    B/op

Время выполнения сократится более чем в 2,5 раза, при этом разница в потреблении памяти составит всего 20%. Если же имя класса будет ещё длиннее


private final Class<?> klass = org.springframework.objenesis.instantiator.perc.PercSerializationInstantiator.class;

то String.replace(char, char) будет выигрывать как по времени, так и по памяти:


                                     Mode     Score     Error   UnitsmanualReplace                        avgt   212,368    3,370   ns/opstringReplace                        avgt    75,503    1,028   ns/opmanualReplace:gc.alloc.rate.norm    avgt   360,000    0,001    B/opstringReplace:gc.alloc.rate.norm    avgt   272,000    0,001    B/op

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


// java.lang.AbstractStringBuilderprivate int newCapacity(int minCapacity) {  // overflow-conscious code  int newCapacity = (value.length << 1) + 2;  if (newCapacity - minCapacity < 0) {    newCapacity = minCapacity;  }  return newCapacity <= 0 || MAX_ARRAY_SIZE - newCapacity < 0          ? hugeCapacity(minCapacity)          : newCapacity;}

Поэтому в примере выше потребление памяти выглядит следующим образом:


java.lang.String                        16 знаков  16 ячеекt.s.b.s.CharacterReplaceBenchmark       58 знаков  70 ячеекo.s.o.i.p.PercSerializationInstantiator 77 знаков  142 ячейки

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


// com.intellij.internal.statistic.beans.ConvertUsagesUtilchar c = text.charAt(i);switch (c) {  case GROUP_SEPARATOR:  case GROUPS_SEPARATOR:  case GROUP_VALUE_SEPARATOR:  case '\'':  case '\"':  case '=' :    escaped.append(' ');    break;  default:    escaped.append(c);    break;}

Если переписать это с использованием String.replace(char, char), то получится следующая цепочка:


return text  .replace(GROUP_SEPARATOR, ' ')  .replace(GROUPS_SEPARATOR, ' ')  .replace(GROUP_VALUE_SEPARATOR, ' ')  .replace('\'', ' ')  .replace('\"', ' ')  .replace('=' , ' ');

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



Выводы для разработчика:


  • неразрывное действие лучше, чем цикл
  • разовое выделение памяти быстрее, чем многократное
  • массовые операции в 99 случаях из 100 выигрывают у одиночных
  • из любого правила бывают исключения в 1 случае из 100

StringJoiner: склеивание через разделитель


Смотревшие доклад lany Java 9-14: Маленькие оптимизации знают про JDK-8054221, а именно улучшенную реализацию StringJoiner-а:


// былоpublic final class StringJoiner {  private final String prefix;  private final String delimiter;  private final String suffix;  private StringBuilder value;}// сталоpublic final class StringJoiner {  private final String prefix;  private final String delimiter;  private final String suffix;  private String[] elts;  private int size;  private int len;}

Самое праздничное во всём этом: StringBuilder.toString():


char[] chars = new char[len + addLen];int k = getChars(prefix, chars, 0);if (size > 0) {  k += getChars(elts[0], chars, k);  for (int i = 1; i < size; i++) {    k += getChars(delimiter, chars, k);    k += getChars(elts[i], chars, k);  }}k += getChars(suffix, chars, k);return new String(chars);

Зная подробности реализации можно использовать StringJoiner в задаче склеивания множества строк без разделителя:


StringBuilder pathBuilder = new StringBuilder();for (PathComponent pathComponent : pathComponents) {  pathBuilder.append(pathComponent.getPath());}return pathBuilder.toString();

лёгким движением руки превращается в


StringJoiner pathBuilder = new StringJoiner("");for (PathComponent pathComponent : pathComponents) {    pathBuilder.add(pathComponent.getPath());}return pathBuilder.toString();

что даёт прирост на больших объёмах данных, особенно для нелатинских строк:


                         latin  length    Mode     Score    Error   Unitssb                        true      10    avgt     122,2     5,0   ns/opsb                        true     100    avgt     463,5    42,6   ns/opsb                        true    1000    avgt    3446,6   109,1   ns/opsj                        true      10    avgt     141,1     5,3   ns/opsj                        true     100    avgt     356,0     6,9   ns/opsj                        true    1000    avgt    2522,1   287,7   ns/opsb                       false      10    avgt     229,8    14,7   ns/opsb                       false     100    avgt     932,4     8,7   ns/opsb                       false    1000    avgt    7456,4   527,2   ns/opsj                       false      10    avgt     192,6    70,8   ns/opsj                       false     100    avgt     577,7    60,3   ns/opsj                       false    1000    avgt    3541,9   135,0   ns/opsb:gc.alloc.rate.norm    true      10    avgt     512,0     0,0    B/opsb:gc.alloc.rate.norm    true     100    avgt    4376,0     0,0    B/opsb:gc.alloc.rate.norm    true    1000    avgt   41280,0     0,0    B/opsj:gc.alloc.rate.norm    true      10    avgt     536,0    14,9    B/opsj:gc.alloc.rate.norm    true     100    avgt    3232,0    12,2    B/opsj:gc.alloc.rate.norm    true    1000    avgt   30232,0    12,2    B/opsb:gc.alloc.rate.norm   false      10    avgt    1083,2     7,3    B/opsb:gc.alloc.rate.norm   false     100    avgt    9744,0     0,0    B/opsb:gc.alloc.rate.norm   false    1000    avgt   93448,0     0,0    B/opsj:gc.alloc.rate.norm   false      10    avgt     768,0    12,2    B/opsj:gc.alloc.rate.norm   false     100    avgt    5264,0     0,0    B/opsj:gc.alloc.rate.norm   false    1000    avgt   50264,0     0,0    B/op

Теперь посмотрите на код и постарайтесь найти в нём недоработку:


char[] chars = new char[len + addLen];int k = getChars(prefix, chars, 0);if (size > 0) {  k += getChars(elts[0], chars, k);  for (int i = 1; i < size; i++) {    k += getChars(delimiter, chars, k);    k += getChars(elts[i], chars, k);  }}k += getChars(suffix, chars, k);return new String(chars);

Ответ
char[] chars = new char[len + addLen];     // почему char[], а не byte[] ?!!int k = getChars(prefix, chars, 0);if (size > 0) {  k += getChars(elts[0], chars, k);  for (int i = 1; i < size; i++) {    k += getChars(delimiter, chars, k);    k += getChars(elts[i], chars, k);  }}k += getChars(suffix, chars, k);return new String(chars);

А вот это уже совсем другая история. Если совсем коротко, то причина в пакете: StringJoiner лежит в java.util, а весь функционал связанный со сжатыми строками в java.lang. Поэтому внутри StringBuider-а массив байтов, а в StringJoiner всё ещё char[]. О попытках это исправить я подробно писал в прошлой статье.


Выводы:


  • старайтесь избегать выражений вроде map.get(/* new String */) / map.put(/* new String */)
  • составной ключ вида "_" + smth почти всегда можно заменить
  • при буферизации обращайте внимание на объём данных и размер буфера
  • клейте строки через +, зачастую StringBuilder не нужен
  • одиночные преобразования почти всегда проигрывают массовым
  • помните о StringJoiner-e и используйте его для типовых задач

Пишите свои примеры в комментариях, будем разбирать.

Подробнее..

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru