Узкое место
Код для построения этих таблиц весьма прост:
В теперешнем варианте – в зависимости от ввода – спам-фильтр стал работать от пяти до десяти раз быстрее, чем в версии с улучшенной strstг, и от семи до пятнадцати раз быстрее, чем в исходной реализации. Мы не достигли показателя в 52 раза – отчасти из-за неравномерного распределения букв, отчасти из-за того, что цикл в новом варианте стал более сложным, и отчасти из-за неизбежного выполнения бессмысленных сравнений строк, но все же спам-фильтр перестал быть слабым звеном в обеспечении доставки почты. Проблема производительности решена.
Оставшаяся часть главы будет посвящена технологиям, используемым для выявления проблем производительности, вычленения медленного кода и его ускорения. Однако перед тем, как двигаться дальше, обратимся еще раз к спам-фильтру и посмотрим, чему же он нас научил. Самое главное – убедиться, что производительность имеет критическое значение. Во всех наших действиях не было бы никакого смысла, если бы спам-фильтр не являлся узким местом почтовой системы.
Поскольку мы знали, что проблема заключается именно в нем, мы применили профилирование и другие технологии для изучения его поведения и выяснения главных недостатков. Далее мы убедились, что проблема сформулирована правильно и решать надо именно ее – глобально, а не концентрироваться на улучшении strstr, на которую падало небезосновательное, однако же, неверное подозрение. Наконец, мы решили эту проблему, применив более удачный алгоритм, и, проверив, выяснили, что скорость действительно возросла. Поскольку она возросла в достаточной степени, мы остановились – зачем заниматься ненужными усовершенствованиями?
Упражнение 7.1
Таблица, которая соотносит отдельный символ с набором образцов, начинающихся с него, стала основой существенного повышения производительности. Напишите версию isspam, которая использует в качестве индекса два символа. Насколько это будет лучше? Это – простейший особый случай структуры данных, которая называется "бор" (trie). Большинство подобных структур данных основаны на затратах места ради экономии времени.