Раньше использовал BeautifulSoup, сейчас пользуюсь html5lib (с xpath). Последний заметно корректнее разбирает кривой HTML, но он и медленнее. Быстрых альтернатив этим библиотекам нет, либо они мне не известны.
Что касается html5lib. Этот пакет формирует DOM, дальше я использую xpath. Скорость сравнивал только по связке html5lib + xpath, как я сказал это медленнее супа. Возможно я делал неоптимальные запросы xpath.
..bw