Boost Xpressive — почему случай сбоя этого регулярного выражения экспоненциальный?

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

отметка времени: {список значений через запятую}

куда
отметка времени не подписана
значения не подписаны

Для этого я использовал следующее регулярное выражение, используя boost :: xpressive

std::vector< uint32_t > idleReports;
uint32_t timestamp = 0;

sregex cpuIdleVal = ( +_d )[ push_back( xp::ref( idleReports ), as<unsigned>( _ ) ) ];
sregex cpuIdleData = cpuIdleVal >> "," | cpuIdleVal;
sregex fullMatch = ( +_d )[ xp::ref( timestamp ) = as<unsigned>( _ ) ]
>> ":" >> +cpuIdleData;
smatch what;
if( regex_match( test, what, fullMatch ) )
{
// stuff
}

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

"1381152543:988900,987661,990529,987440,989041,987616,988185,988346,968859,988919,859559,988967,991040,988942"

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

Если значение 5 является отрицательным, время, затрачиваемое еще больше.

Почему производительность так плохо для случаев отказа?

Я исправил проблему, изменив исходное регулярное выражение на:

sregex cpuIdleData = "," >> cpuIdleVal;
sregex fullMatch =  ( +_d )[ xp::ref( timestamp ) = as<unsigned>( _ ) ]
>> ":" >> cpuIdleVal >> -+ cpuIdleData ;

то есть сделать сопоставление со списком через запятую не жадным.

В измененной версии сценарии сбоев работают так же хорошо (или немного лучше) сценариев успеха.