search

dropbox / zxcvbn-ios

A realistic password strength estimator.
https://tech.dropbox.com/2012/04/zxcvbn-realistic-password-strength-estimation/
MIT License
223 stars 64 forks source link

It gets very slow for some password lengths #7

Closed duzun closed 9 years ago

duzun commented 9 years ago

For password testScorePassword123 it takes 0.5 sec to compute the score, which is A LOT!

It looks like there is some high complexity algorithm, cause time grows exponentially after some length.

jessemx109 commented 9 years ago

This happens because DBMatcher's are being allocated multiple times which is loading the frequency lists using lots of memory. If you put the frequency list initialization in a singleton it stops the memory leak and makes performance good again

duzun commented 9 years ago

This is not the case. DBMatcher is alocated exactly once in [DBZxcvbn init]; Acording to my tests, most of the time is spent inside this call: DBResult *result = [self.scorer minimumEntropyMatchSequence:password matches:matches];

jessemx109 commented 9 years ago

In the spacialEntropy call in DBScorer the allocate method is called again. I believe this method is only called on long passwords and thats why the slowdown only happens on longer passwords

duzun commented 9 years ago

IF DBMatcher is so slow, I think it should share the data between instances, with the posibillity to free it when needed.

jessemx109 commented 9 years ago

Thats what I did to fix it I wrapped the initialization of the frequency lists and adjacency graphs in a singleton object so they are only ever created once and it sped up the performance significantly

leah commented 9 years ago

@jessemx109 want to submit a pull request with that change? That would be really nice :smile:

erikackermann commented 9 years ago

:+1: would appreciate that performance boost

leah commented 9 years ago

I think this was done in #8?

Closing this issue but feel free to re-open if there's more we can do to improve this.