:zip: #2106 tokenizer.tokenize speed improvement (3-8x) by caching added_tokens in a Set
Author: mandubian
Pull request: yes

in #2106, we see that adding tokens to tokenizer decreases progressively tokenization performance which is not really a surprise as you need to go through the list of tokens which grows. But it sounds that this increase is not linear.

By having a quick look at code, I've seen that:
- `added_tokens` list is built for every calls of tokenize,
- `all_special_tokens` is a python property that is reevaluated every time
- `split_on_tokens` is going 2x in both `all_special_tokens` and `added_tokens_encoder` lists which is `O(n)`.

I've tried to replace those by a simple cached Set of `added_tokens_encoder.keys() + all_special_tokens` that is reevaluated at each call of `add_tokens`. firstly, it avoids rebuilding the list at every call. Secondly, searching in a Set is `O(1)` in average and `O(n)` in worst case.

On RobertaTokenizer, the result is a significant speed improvement (testing on for 100.000 calls):
- for 0 added token, `tokenizer.tokenize` is >3x faster
- for 200 tokens, `tokenizer.tokenize` is >7x faster

Here are a few interesting plots.

### Execution time when adding more tokens between old code and new
<img width="404" alt="Screenshot 2019-12-14 at 15 34 22" src="https://user-images.githubusercontent.com/77193/70850213-167e8f80-1e88-11ea-8339-334ada7e5f37.png">

We see here that old code is not linear and the execution time is impacted when more tokens are added.
New code seems to behave linearly (up to 200 at least)

### Rate of speed increase between old code and new
<img width="372" alt="Screenshot 2019-12-14 at 15 33 09" src="https://user-images.githubusercontent.com/77193/70850210-036bbf80-1e88-11ea-9778-d59e1e3e83c7.png">

We see that new code is 3x faster by default and this advantage grows when adding more tokens (>7x for 200)

### Execution time between old code and new in a bar plot

<img width="399" alt="Screenshot 2019-12-14 at 15 33 14" src="https://user-images.githubusercontent.com/77193/70850206-fe0e7500-1e87-11ea-808e-1c9043a5ec4b.png">

Same as previous plot.

I know you're working on Rust tokenizers that will be much faster in theory. But until it's ready, what do you think about this basic correction (and maybe others) that already improves the speed drastically?

Don't hesitate to tell if you see that this modification would be very bad for other cases.



Comments:
# [Codecov](https://codecov.io/gh/huggingface/transformers/pull/2177?src=pr&el=h1) Report
> Merging [#2177](https://codecov.io/gh/huggingface/transformers/pull/2177?src=pr&el=desc) into [master](https://codecov.io/gh/huggingface/transformers/commit/e92bcb7eb6c5b9b6ed313cc74abaab50b3dc674f?src=pr&el=desc) will **increase** coverage by `<.01%`.
> The diff coverage is `100%`.

[![Impacted file tree graph](https://codecov.io/gh/huggingface/transformers/pull/2177/graphs/tree.svg?width=650&token=9qOlN6Hb1c&height=150&src=pr)](https://codecov.io/gh/huggingface/transformers/pull/2177?src=pr&el=tree)

```diff
@@            Coverage Diff             @@
##           master    #2177      +/-   ##
==========================================
+ Coverage   81.35%   81.36%   +<.01%     
==========================================
  Files         120      120              
  Lines       18254    18256       +2     
==========================================
+ Hits        14851    14854       +3     
+ Misses       3403     3402       -1
```


| [Impacted Files](https://codecov.io/gh/huggingface/transformers/pull/2177?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [transformers/tokenization\_utils.py](https://codecov.io/gh/huggingface/transformers/pull/2177/diff?src=pr&el=tree#diff-dHJhbnNmb3JtZXJzL3Rva2VuaXphdGlvbl91dGlscy5weQ==) | `90.74% <100%> (+0.24%)` | :arrow_up: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/huggingface/transformers/pull/2177?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/huggingface/transformers/pull/2177?src=pr&el=footer). Last update [e92bcb7...cc01351](https://codecov.io/gh/huggingface/transformers/pull/2177?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).


I've seen there was a similar PR https://github.com/huggingface/transformers/pull/1881 but focusing on special tokens. The current one is a bit more generic IMHO. You'll tell me what you think about it.

Thank you for the detailed report, this is very cool. It looks good to me, great work @mandubian!

Awesome, thanks a lot @mandubian