Низкоуровневая оптимизация в Java?

Май 25th, 2009 по SadKo Оставить ответ »

По работе пришлось столкнуться с парсером файлов. Нужно парсить относительно простые структуры любой вложенности. Собственно говоря, для этого возникла необходимость написать токенайзер (заранее извиняюсь, если правильное название этой штуке будет разборщик лексем).
Соответственно, без посимвольного разбора не обойтись. Вариантов получения символов два: либо из CharSequence, либо из InputStream. Когда был готов алгоритм, скорость разбора строки меня не впечатлила: всего около 100 строк в секунду.
Почему? Давайте разбираться.


Замечу, что InputStream не имеет возможности читать файлы построчно — он работает только с байтами. Поэтому для чтения файла я использовал:

String line = RandomAccessFile.readLine();

После этого создавал ByteArrayInputStream и парсил структуры вот таким образом:

InputStream bais = new ByteArrayInputStream(line.getBytes());
parser.parseOptionSet(bais); // парсинг структуры, записанной в линию

Показатель 100 строк/секунду меня не удовлетворил, поэтому решил всё-таки заменить RandomAccessFile на BufferedReader, примерно так:

InputStream file = new FileInputStream("misc/many_sets.cfg");
BufferedReader fd = new BufferedReader(new InputStreamReader(file));
while ((line = fd.readLine())!=null)
    parser.parseOptionSet(line);

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

CharSequence m_Buffer;
int m_Column = 0;

protected Character getChar() throws IOException
{
	try
	{
		char ch = m_Buffer.charAt(m_Column);
		m_Column++;
		return ch;
	}
	catch (IndexOutOfBoundsException ex)
	{
		return null;
	}
}

То есть, метод возвращал либо объект типа Character, либо null, если ловил IndexOutOfBoundsException.

Запустил систему, производительность возросла где-то в 5 раз (!!!). Но и это не предел.

Надо сказать, что структуры, которые следует создавать, писал не я, и они делались атомарными (thread-safe). Тем не менее, я покопался в коде и в некоторых местах поубирал лишние synchronized-блоки (что не нарушало целостности логики работы со структурами). Производительность поднялась где-то ещё на 50 строк в секунду.

Но показатель в 600 строк в секунду меня тоже не удовлетворил. Тогда я ещё раз взглянул на функцию getChar() и добавил эту проверку:

if (m_Buffer.length() <= m_Column)
	return null;

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

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

private final Tm_Token getSection() throws IOException, Ex_ParsingException
{
	StringBuilder result = new StringBuilder(32);
	Character ch;
		
	// Main parsing cycle
	while ((ch = getChar())!=null)
	{
		switch (ch)
		{
			// Closing brace?
			case ']':
				return createToken(En_TokenType.SECTION, result.toString().trim());
				
			// Another character?
			default:
				result.append(ch);
		}
	}
		
	throw new Ex_ParsingException("Unclosed section identifier at line=" + getLastLine() + ", column=" + getLastColumn());
}

Производительность выросла, но не настолько, насколько бы хотелось. Тем не менее, ещё около 100 строк в секунду я выжал из парсера.

Но каково же велико было моё удивление, когда я обнаружил, как работает метод StringBuilder.append(). Так как JDK теперь поставляется с исходниками (вот она, мощь OpenSource!), я не поленился поглядеть implementation метода append. И что же я обнаружил? А вот что:

class StringBuilder
{
//...
    public StringBuilder append(Object obj) {
	return append(String.valueOf(obj));
    }
//...
}

class String
{
//...
    public static String valueOf(Object obj) {
	return (obj == null) ? "null" : obj.toString();
    }
//...
}

Ужас! На каждый Character создаётся объект типа String, после чего только вызывается Append, но уже на этом объекте. Тогда я просто заменил Character на char вот таким образом:

	private final Tm_Token getSection() throws IOException, Ex_ParsingException
	{
		StringBuilder result = new StringBuilder(32);
		Character ch;
		
		// Main parsing cycle
		while ((ch = getChar())!=null)
		{
			char ch_val = ch.charValue();
			
			switch (ch_val)
			{
				// Closing quotes?
				case ']':
					return createToken(En_TokenType.SECTION, result.toString().trim());
				
				// Another character?
				default:
					result.append(ch_val);
			}
		}
		
		throw new Ex_ParsingException("Unclosed section identifier at line=" + getLastLine() + ", column=" + getLastColumn());
	}

И (о чудо)! Скорость парсинга резко возросла до 1800 строк в секунду. И это, скорее всего, ещё не предел.
Итого, имеем следующие результаты тестов:

Start time:          1243012146763 milliseconds
Stop time:           1243012157855 milliseconds
Total lines:         20748 lines
Total bytes:         44815680 bytes
Total time:          11092 milliseconds (11,092 seconds)
Average line length: 2160,00 bytes
Average speed:       1870,54 lines/second, 4040360,62 bytes/second

То есть, после оптимизации на среднем и низком уровне скорость работы алгоритма была увеличена примерно в 18 раз!

Поэтому об оптимизации на более низких уровнях в Java надо тоже задумываться :) .

Реклама

4 комментариев

  1. Анонимно:

    Это разве низкий уровень?

    Я уж подумал было что ты прям в байткоде оптимизировал. :)
    А так — это просто алгоритмическая оптимизация.

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

  2. Ай, маладца!

    А чего мозги парил, раз сам разобралсо!?

    > Поэтому об оптимизации на более низких уровнях в Java надо тоже задумываться :)

    JNI+C+ASM тебе в помощь! ;)

  3. Re: Ай, маладца!

    Думал, будет другим полезно :) .
    Проблема C+ASM в том, что они платформозависимы. Не, можно, конечно, написать токенайзер+парсер, и работать он будет на порядок быстрее. Но встаёт логичный вопрос: что делать с переносом такой системы под тот же виндоус? А то бывают и такие шизанутые заказчики, которым сервак на венде подавай.

  4. Re: Это разве низкий уровень?

    Не, это наша проприетарная библиотека парсинга конфигураций :) .

Добавить комментарий

Blue Captcha Image
Refresh

*