LlamaTokenizer is unbearably slow when dealing with large strings
Author: Vectorrent
Pull request: no

### System Info

- `transformers` version: 4.34.1
- Platform: Linux-6.5.9-arch2-1-x86_64-with-glibc2.35
- Python version: 3.10.12
- Huggingface_hub version: 0.17.3
- Safetensors version: 0.4.0
- Accelerate version: 0.24.1
- Accelerate config:    not found
- PyTorch version (GPU?): 2.1.0+cu121 (True)
- Tensorflow version (GPU?): not installed (NA)
- Flax version (CPU?/GPU?/TPU?): not installed (NA)
- Jax version: not installed
- JaxLib version: not installed
- Using GPU in script?: true
- Using distributed or parallel set-up in script?: false

### Who can help?

@ArthurZucker @younesbelkada 

### Information

- [ ] The official example scripts
- [X] My own modified scripts

### Tasks

- [ ] An officially supported task in the `examples` folder (such as GLUE/SQuAD, ...)
- [X] My own task or dataset (give details below)

### Reproduction

Here is a simplified example of what I'm trying to do:
```
from transformers import AutoTokenizer

text = <very_large_string>

tokenizer = AutoTokenizer.from_pretrained(
    "mistralai/Mistral-7B-v0.1",
    padding="max_length",
    padding_side="left",
    return_overflowing_tokens=True,
    truncation=True,
)

tokenized = tokenizer(
    text,
    max_length=1024,
    stride=64,
    padding="max_length",
    return_overflowing_tokens=True,
    truncation=True,
    return_tensors="np",
)
```
I also tested the `PY007/TinyLlama-1.1B-intermediate-step-480k-1T` implementation of the `LlamaTokenizer`, and it has the same problem. Tokenization is really, really slow.

[Here is a link to my tokenization code](https://github.com/LuciferianInk/aigen/blob/9bc76f074053f6e5907cdf2072b70d7f4eac383a/aigen/TokenDataset.py#L131), and [here is a link to the Dockerfile that represents my entire training environment](https://github.com/0-5788719150923125/vtx/blob/main/Dockerfile.x64).

### Expected behavior

When tokenizing very large strings with the `LlamaTokenizerFast`, progress is unbearably slow. Even worse, progress becomes slower and slower as the length of a string increases. For example:

**Test String 1** (LlamaTokenizer)
768 batches, 1024 tokens each
4 seconds total
0.005 seconds/batch average

**Test String 2** (LlamaTokenizer)
141473 batches, 1024 tokens each
9600 seconds total
0.068 seconds/batch average

By comparison, if I use the `GPTNeoXTokenizerFast` tokenizer:

**Test String 1** (GPTNeoXTokenizer)
68 batches, 2048 tokens each
0.06 seconds total
0.0009 seconds/batch average

For every other tokenizer I've used, performance is tolerable. `LlamaTokenizer`, however, has abysmal performance, and I'm not sure why. Some things I've observed:

- Other tokenizers will consume a ton of system memory, as they tokenize large strings. `LlamaTokenizer` doesn't do that. Memory usage stays very low, and constant; it doesn't grow at all.
- Adjusting the `TOKENIZERS_PARALLELISM` environment variable seems to have little to no effect.
- `use_fast=False` does not fix my problem.

I'm not sure what to try at this point, and I would appreciate any advice you have. This is an incredibly frustrating problem. Whereas my standard dataset would typically take no longer than 30 minutes to tokenize, this one is going to take a full 24+ hours, at the rate its going now! Clearly, something is wrong; I'm just not sure if it's my environment, or a bug.

Thanks in advance for any assistance you can provide.

Comments:
Alright, well it seems like the clear solution is to use a batched tokenization strategy. Here's what I'm doing now (though I'm not sure if this is the best method):
```
block_size = 1024
batch_size = 100000
content = <my_very_large_string>

batches = [
    content[i : i + batch_size] for i in range(0, len(content), batch_size)
]
tokenized_batches = []
with tqdm(total=len(batches)) as pbar:
    for batch in batches:
        tokenized = tokenizer(
            batch,
            max_length=block_size,
            stride=stride,
            padding="max_length",
            return_overflowing_tokens=True,
            truncation=True,
            return_tensors="np",
        )
        tokenized_batches.append(tokenized["input_ids"])
        pbar.update(1)

tokens = np.concatenate(tokenized_batches)
```
I would appreciate if anyone could let me know if there is a more-optimal way to do this batching. I can already see a problem in the current implementation, where each batch is going to end with a bunch of padding that wouldn't be there otherwise (if we tokenized the entire string in one batch).

Hey, this seems to be related to #25873, but yes you should use the `tokenizer.batch_encode` (or just `encode` which supports batch of strings for the fast version, while the slow should be alright. 
I can still try to run some benchmarks on whether or not the latest updates have significantly slowed down the encoding / decoding (this is on my todo list!) 


This issue has been automatically marked as stale because it has not had recent activity. If you think this still needs to be addressed please comment on this thread.

Please note that issues that do not follow the [contributing guidelines](https://github.com/huggingface/transformers/blob/main/CONTRIBUTING.md) are likely to be ignored.