Improve the speed of adding tokens from added_tokens.json
Author: cchen-dialpad
Pull request: yes

# What does this PR do?

This PR significantly improves the speed of adding tokens from `added_tokens.json`, when it contains a large number of tokens (e.g., 20,000+). When adding one token at a time, it uses `bisect` to insert the token into `PreTrainedTokenizer.unique_no_split_tokens`. Please see a detailed description and motivation in this issue: https://github.com/huggingface/transformers/issues/10676

This change relies on the requirement that `unique_no_split_tokens` is sorted. (I'm not sure if this is a fair assumption, otherwise I can check if it's already sorted before the insertion.)

Fixes #10676


## Benchmark
MacOS Mojave (CPU: 2.6 GHz Intel Core i7)
python==3.7.9
torch==1.7.1+cpu
transformers==3.5.1 or transformers==4.4.2 (similar results)

```python
import json
from timeit import default_timer as timer
from transformers import DistilBertTokenizer

model_dir = '/home/username/saved_model'

# Load a pretrained model's tokenizer, save it to {model_dir}
tokenizer = DistilBertTokenizer.from_pretrained('distilbert-base-uncased')
tokenizer.save_pretrained(model_dir)
print('len(tokenizer) of a pretrained model distilbert-base-uncased:', len(tokenizer))

# Generate n values as token suffix, to randomize the insertion position of added tokens
low = 30522
high = 82181   # exclusive
random_suffix = list(range(low, high))
random.shuffle(random_suffix)

# Save the n new tokens with correct indices to added_tokens.json
added_tokens = {f'addedtoken{val}': low + idx for idx, val in enumerate(random_suffix)}
with open(f'{model_dir}/added_tokens.json', 'w') as f:
    json.dump(added_tokens, f)
print(f'saved {len(added_tokens)} tokens to added_tokens.json')

# Load the tokenizer from {model_dir}, and print the elapsed time
start = timer()
tokenizer = DistilBertTokenizer.from_pretrained(model_dir)
print('len(tokenizer) after loading from saved model:', len(tokenizer))
end = timer()
print('Elapsed (seconds):', round(end - start, 3))

# Make sure tokenizer.unique_no_split_tokens remains sorted
all_values = tokenizer.unique_no_split_tokens
assert all(all_values[i+1] > all_values[i] for i in range(len(all_values) - 1))
```

**If we save 21659 tokens in added_tokens.json**, output before the change:
```bash
len(tokenizer) of a pretrained model distilbert-base-uncased: 30522
saved 21659 tokens to added_tokens.json
len(tokenizer) after loading from saved model: 52181
*** Elapsed (seconds): 76.95
```

output after the change:
```bash
len(tokenizer) of a pretrained model distilbert-base-uncased: 30522
saved 21659 tokens to added_tokens.json
len(tokenizer) after loading from saved model: 52181
*** Elapsed (seconds): 0.308
```

**If we save 51659 tokens in added_tokens.json**, output before the change:
```bash
len(tokenizer) of a pretrained model distilbert-base-uncased: 30522
saved 51659 tokens to added_tokens.json
len(tokenizer) after loading from saved model: 82181
*** Elapsed (seconds): 527.795
```

output after the change:
```bash
len(tokenizer) of a pretrained model distilbert-base-uncased: 30522
saved 51659 tokens to added_tokens.json
len(tokenizer) after loading from saved model: 82181
*** Elapsed (seconds): 0.83
```

<!--
Congratulations! You've made it this far! You're not quite done yet though.

Once merged, your PR is going to appear in the release notes with the title you set, so make sure it's a great title that fully reflects the extent of your awesome contribution.

Then, please replace this with a description of the change and which issue is fixed (if applicable). Please also include relevant motivation and context. List any dependencies (if any) that are required for this change.

Once you're done, someone will review your PR shortly (see the section "Who can review?" below to tag some potential reviewers). They may suggest changes to make the code even better. If no one reviewed your PR after a week has passed, don't hesitate to post a new comment @-mentioning the same persons---sometimes notifications get lost.
-->

<!-- Remove if not applicable -->

## Who can review?

@lhoestq @LysandreJik 

<!-- Your PR will be replied to more quickly if you can figure out the right person to tag with @

 If you know how to use git blame, that is the easiest way, otherwise, here is a rough guide of **who to tag**.
 Please tag fewer than 3 people.

Models:

- albert, bert, xlm: @LysandreJik
- blenderbot, bart, marian, pegasus, encoderdecoder,  t5: @patrickvonplaten, @patil-suraj
- longformer, reformer, transfoxl, xlnet: @patrickvonplaten
- fsmt: @stas00
- funnel: @sgugger
- gpt2: @patrickvonplaten, @LysandreJik
- rag: @patrickvonplaten, @lhoestq
- tensorflow: @LysandreJik

Library:

- benchmarks: @patrickvonplaten
- deepspeed: @stas00
- ray/raytune: @richardliaw, @amogkam
- text generation: @patrickvonplaten
- tokenizers: @n1t0, @LysandreJik
- trainer: @sgugger
- pipelines: @LysandreJik

Documentation: @sgugger

HF projects:

- nlp datasets: [different repo](https://github.com/huggingface/nlp)
- rust tokenizers: [different repo](https://github.com/huggingface/tokenizers)

Examples:

- maintained examples (not research project or legacy): @sgugger, @patil-suraj
- research_projects/bert-loses-patience: @JetRunner
- research_projects/distillation: @VictorSanh

 -->


Comments:
Hi! Could you provide a way to benchmark the change so that we can see in which situations is the speedup visible? Thank you!

> Hi! Could you provide a way to benchmark the change so that we can see in which situations is the speedup visible? Thank you!

Hi @LysandreJik , I just updated the benchmark code snippets and sample output in the description. Hopefully it can validate the change.

Hi @LysandreJik , just wanted to follow up on this, is there anything else you would like to see on this PR? I also tried to run the slow test. It looked ok, but with a few connection errors: `ValueError: Connection error, and we cannot find the requested files in the cached path. Please try again or make sure your Internet connection is on`, and re-run didn't fix it. I was wondering how the slow tests look like on your end. Thanks!

Awesome, thanks to both of you!