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

# 🚀 Feature request

<!-- A clear and concise description of the feature proposal.
     Please provide a link to the paper and code in case they exist. -->

~~Make `PreTrainedTokenizer.unique_no_split_tokens` a type `Set[str]`, or use a temporary `Set[str]` variable for adding tokens from `added_tokens.json`.~~

(**Update**) Found one old PR related to this: https://github.com/huggingface/transformers/pull/6461
So instead of changing its type to `Set[str]`, it would be great to slightly modify the way how tokens are added to `PreTrainedTokenizer.unique_no_split_tokens`. Assume `unique_no_split_tokens` is always ordered and deduped during the token adding process, we could do something like below:

```python
import bisect

# add this function to transformers/src/transformers/tokenization_utils.py
def _insert_one_token(token_list: List[str], new_token: str):
    # search if new_token is already in the ordered token_list
    insertion_idx = bisect.bisect_left(token_list, new_token)
    if insertion_idx < len(token_list) and token_list[
        insertion_idx] == new_token:
        # new_token is in token_list, don't add
        return
    else:
        token_list.insert(insertion_idx, new_token)
```

Then at https://github.com/huggingface/transformers/blob/26a33cfd8c2d6923f41ab98683f33172e8948ff3/src/transformers/tokenization_utils.py#L200-L205

Do something like this:
```python
if special_tokens:
    if len(new_tokens) == 1:
        _insert_one_token(self.unique_no_split_tokens, new_tokens[0])
    else:
        self.unique_no_split_tokens = sorted(set(self.unique_no_split_tokens).union(set(new_tokens)))
else:
    # Or on the newly added tokens
    if len(tokens_to_add) == 1:
        _insert_one_token(self.unique_no_split_tokens, tokens_to_add[0])
    else:
        self.unique_no_split_tokens = sorted(set(self.unique_no_split_tokens).union(set(tokens_to_add)))
```

My local tests show that this can reduce the token adding time from 9 mins (see details below) down to about 1 seconds.


## Motivation

<!-- Please outline the motivation for the proposal. Is your feature request
     related to a problem? e.g., I'm always frustrated when [...]. If this is related
     to another GitHub issue, please link here too. -->

Currently the `unique_no_split_tokens` is of type `List[str]`: https://github.com/huggingface/transformers/blob/26a33cfd8c2d6923f41ab98683f33172e8948ff3/src/transformers/tokenization_utils.py#L123

This causes a performance issue if the number of added tokens from `added_tokens.json` is large, when running `tokenizer.from_pretrained()`. For example, it takes 9 minutes to add about 50000 new tokens on a MacBook Pro (2.6 GHz Intel Core i7). Specifically, the issue is mainly caused by:
https://github.com/huggingface/transformers/blob/26a33cfd8c2d6923f41ab98683f33172e8948ff3/src/transformers/tokenization_utils.py#L200-L205

Tokens in `added_tokens.json` are added **one by one,** https://github.com/huggingface/transformers/blob/26a33cfd8c2d6923f41ab98683f33172e8948ff3/src/transformers/tokenization_utils_base.py#L1827-L1832

 so the `set` operation will be repeated 50000 times, with more and more number of elements. ~~By switching to `Set[str]` or using a temporary `Set[str]` variable for token adding purpose, it would significantly lower the overhead when adding tokens from `added_tokens.json`, and also helps a few `in` presence checks in a few places.~~ (**Update**: Like pointed out earlier, we don't need to change to `Set[str]`, just using a more efficient way to insert one token into the ordered list should be good enough.)


Comments:
@lhoestq If this looks good to you, I can help create a PR. Thanks!

Hi !
This looks like a great solution, feel free to open a PR ! :)

Great, thanks! Just made a PR here: https://github.com/huggingface/transformers/pull/10780