facebook / facebook/hhvm

Static strings table can degrade to O(N) performance

Open
#7,126 3 comments 0 reactions 0 assignees View on GitHub
mid-pri performance
Dominant language
C++
Stars
18.7k
Forks
3.1k
Avg merge
1h 47m
Merged PRs (30d)
2

Description

Increasing hhvm.server.thread_count can lead to the static strings table degrading to O(N) performance instead of the expected O(1) performance, with potentially severe effect on an application.

The AtomicHashMap backing the static string table can exceed its configured maxLoadFactor, and the amount of overrun is dependent on the number of threads. (See facebook/folly#420 for details.) This gives a "true" max load factor of:

`(1 + entryCountThreadCacheSize * thread_count / initial_static_string_table_size) * maxLoadFactor`

Under default HHVM settings and increasing thread_count, at 120 threads the maximum possible load factor is 96% and there is likely to be some degree of performance degradation. At 125 threads the load factor reaches 1.0 and it becomes possible for a find() or insert() to require iterating the entire hashtable of 625,000 entries. Further increasing thread_count increases the likelihood of landing in this state.
### HHVM Version

HipHop VM 3.12.1 (rel)
### Standalone code, or other way to reproduce the problem

This case is difficult to compactly reproduce since I'm unsure how data winds up in the static strings table.

Our application performs periodic jobs that require parsing batches of INI files. Once the static strings table reaches a size over 625,000 over the course of hours or days of steady service, calling PHP parse_ini_file() or parse_ini_string() may take several minutes to return, since the [INI parser calls find()](https://github.com/facebook/hhvm/blob/HHVM-3.12.1/hphp/runtime/base/ini-setting.cpp#L531) for every identifier-like token. Worse, since INI parsing [takes a global mutex](https://github.com/facebook/hhvm/blob/HHVM-3.12.1/hphp/runtime/base/ini-setting.cpp#L644), the operation can block many or all threads on the server, causing HHVM to become unresponsive to all requests for minutes or even hours if there is a large batch of INI files to process.
### Expected result

Parsing an INI file takes a consistent and short amount of time (< 1 ms for a 1 KB file)
### Actual result

Parsing an INI file may take several minutes depending on the internal state of the static string table.
### Discussion

I hope to work with the Folly team to find a way to guarantee that AtomicHashMap performance does not pathologically degrade this way. In the interim, it would be nice if HHVM could examine configuration variables to compute the true max load factor and either alert the user or take some corrective action if a dangerous condition is possible.

In particular, the entryCountThreadCacheSize parameter to AtomicHashMap is intended to avoid the cost of an atomic increment on every insert, but HHVM is [already incurring this cost](https://github.com/facebook/hhvm/blob/HHVM-3.12.1/hphp/runtime/server/memory-stats.cpp#L141) by tracking memory usage statistics, so this parameter could be decreased without significantly impacting performance.

Alternatively, some munging of the above expression gives:

`minimum_initial_static_string_table_size = entryCountThreadCacheSize * thread_count / (trueLoadFactor / maxLoadFactor - 1)`

HHVM could compute this based on thread_count and select the larger of either the computed minimum size or the configured size at a moderate memory cost.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.