`LlamaTokenizerFast` very slow with long sequence
Author: SunMarc
Pull request: no

### System Info

- `transformers` version: 4.33.0.dev0
- Platform: Linux-5.15.0-71-generic-x86_64-with-glibc2.35
- Python version: 3.10.11
- Huggingface_hub version: 0.16.4
- Safetensors version: 0.3.2
- Accelerate version: 0.23.0.dev0

- PyTorch version (GPU?): 2.1.0.dev20230810+cu121 (True)
- Tensorflow version (GPU?): 2.11.1 (False)
- Flax version (CPU?/GPU?/TPU?): 0.5.3 (cpu)
- Jax version: 0.3.6
- JaxLib version: 0.3.5
- Using GPU in script?: <fill in>
- Using distributed or parallel set-up in script?: <fill in>

### Who can help?

@ArthurZucker 

### Information

- [ ] The official example scripts
- [ ] My own modified scripts

### Tasks

- [ ] An officially supported task in the `examples` folder (such as GLUE/SQuAD, ...)
- [ ] My own task or dataset (give details below)

### Reproduction
```py
from transformers import AutoTokenizer
from datasets import load_dataset

wikidata = load_dataset('wikitext', 'wikitext-2-raw-v1', split='test')
wikilist = [' \n' if s == '' else s for s in wikidata['text'] ]
# len(text) == 1288556
text = ''.join(wikilist)

model_id = "fxmarty/tiny-llama-fast-tokenizer"
tokenizer = AutoTokenizer.from_pretrained(model_id, use_fast=True)
tokenized = tokenizer(text, return_tensors='pt')
```
### Expected behavior

The tokenizer with `use_fast=True` should not be slower compared to the tokenizer with`use_fast=False`. However, it takes at least 2min for the fast tokenizer while it only takes a few second for the slow tokenizer. 


Comments:
cc @ArthurZucker .

BTW, you don't need to specify `use_fast=True`, `True` is the default value.

Also, could you try to load a pretrained tokenizer from a real checkpoint? Just wondering if this makes a difference.

I tried with `huggyllama/llama-7b` and `meta-llama/Llama-2-7b-hf` and we have the same problem. However, with a tokenizer from `opt` models, it works as expected ! 

This is related to the way `tokenizers` works. If you try:
```python
>>> import time
>>> start=time.time()
>>> tokenizer(wikilist)
>>> print(time.time()-start)
0.12574219703674316 # vs 1.822418451309204 for the slow tokenizer
```
you'll see that it is super fast. This is related to the design of `tokenizers` which is made to be able to run in parallel which you cannot do with a very long text. `OPT`  uses a `GPT2` tokenizer, which is based on ByteLevel BPE, while Llama is a `Sentencepiece` BPE based model, which are not the same
cc @Narsil for a better explanation 😉  

Thank you @ArthurZucker for the explantation. But in the case of short input, it looks bad if it hangs. I don't know the internal and if it is possible to avoid hanging, I am just saying in terms of usgae. Maybe @Narsil has some idea.

I don't think short inputs have any issues
```python 
>>> tokenizer = AutoTokenizer.from_pretrained(model_id, use_fast=False)
>>> import time;start=time.time();tokenizer(text[:2048], return_tensors='pt');print(time.time()-start)
0.005516767501831055

>>> tokenizer = AutoTokenizer.from_pretrained(model_id, use_fast=True)

>>> import time;start=time.time();tokenizer(text[:2048], return_tensors='pt');print(time.time()-start)
0.003057718276977539
``` 

I read your (previous) message wrong, sorry again Sir @ArthurZucker 😭 Thanks!

@ArthurZucker great explanation.

There's a lot to be said around tokenization and especially for super long strings. 
Sentencepiece is "optimized" for super long strings (which almost always exceed model context anyway).

`tokenizers` is build around the assumption that it will see "small" pieces (think whitespace spitted text) and lots of optimizations and caching go with that that enable it to be much faster than sentencepiece in most general situations.
For Lllama that assumption is not true (there is no whitespace splitting, which is actually good as it should work better on non space splitted languages like japanese or chinese.). Sentence splitting should still apply though.

As Arthur pointed out, it's still faster if you tokenize actual sentences independantly, and not concatenated because of parallelism.

Tl;dr different algorithms make different tradeoffs.

Thanks for the explanations ! 

@SunMarc I'm encountering this same issue with long context length. I'm wondering if you just switched to the slow tokenizer in the end or if there are other workarounds? Does the opt models have the same tokenizer by chance? Thanks! 

Hi @jmzeng , you can just switch to the slow tokenizer or you could split the text into sentences and tokenize the sentences before concatenating them. 

Opt's tokenizer is the same as GPT2 which is not the same tokenizer 

Thanks, switching to the slow tokenizer worked quite well for me.