Replace the frequent permutation generations with a pre-allocated permutation table  
Author: FindHao
Pull request: yes

# What does this PR do?

This PR fixes the performance issue in model big_bird. In model bigbird, the random masks are generated each time, and it calls a huge number of `np.random.permutation` which has big overheads. 
 the function `bigbird_block_rand_mask` is only executed when the values of `from_seq_length` and `to_seq_length` are less than [4096](https://github.com/huggingface/transformers/blob/main/src/transformers/models/big_bird/modeling_big_bird.py#L56) and the values of `from_block_size` and `to_seq_length` are 64. With all the above limitations, the number of all possible permutations is less than 249,984. Since all variables mentioned above are configured only once at the initialization stage, we generate all possible permutations at this stage and only randomly generate the indexes by using `numpy.random.randint` when we need permutations.
This optimization significantly reduces the computation on the CPU, and its speedup for the whole model is about 1.12X in TorchBench.

## Before submitting
- [ ] This PR fixes a typo or improves the docs (you can dismiss the other checks if that's the case).
- [x] Did you read the [contributor guideline](https://github.com/huggingface/transformers/blob/main/CONTRIBUTING.md#start-contributing-pull-requests),
      Pull Request section?
- [ ] Was this discussed/approved via a Github issue or the [forum](https://discuss.huggingface.co/)? Please add a link
      to it if that's the case.
- [ ] Did you make sure to update the documentation with your changes? Here are the
      [documentation guidelines](https://github.com/huggingface/transformers/tree/main/docs), and
      [here are tips on formatting docstrings](https://github.com/huggingface/transformers/tree/main/docs#writing-source-documentation).
- [ ] Did you write any new necessary tests?


## Who can review?

Anyone in the community is free to review the PR once the tests have passed. Feel free to tag
members/contributors who may be interested in your PR.

@ArthurZucker and @younesbelkada 

<!-- 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:

- text models: @ArthurZucker and @younesbelkada
- vision models: @amyeroberts and @NielsRogge
- speech models: @sanchit-gandhi
- graph models: @clefourrier

Library:

- flax: @sanchit-gandhi
- generate: @gante
- pipelines: @Narsil
- tensorflow: @gante and @Rocketknight1
- tokenizers: @ArthurZucker
- trainer: @sgugger

Integrations:

- deepspeed: HF Trainer: @stas00, Accelerate: @pacman100
- ray/raytune: @richardliaw, @amogkam

Documentation: @sgugger, @stevhliu and @MKhalusova

HF projects:

- accelerate: [different repo](https://github.com/huggingface/accelerate)
- datasets: [different repo](https://github.com/huggingface/datasets)
- diffusers: [different repo](https://github.com/huggingface/diffusers)
- rust tokenizers: [different repo](https://github.com/huggingface/tokenizers)

Maintained examples (not research project or legacy):

- Flax: @sanchit-gandhi
- PyTorch: @sgugger
- TensorFlow: @Rocketknight1

 -->


Comments:
The docs for this PR live [here](https://moon-ci-docs.huggingface.co/docs/transformers/pr_21499). All of your documentation changes will be reflected on that endpoint.

@ArthurZucker Could you please also help me check the CI errors? In the first CI test 'add model like runner', the error is `src/transformers/models/bigbird_pegasus/modeling_bigbird_pegasus.py:271:21: F821 Undefined name permutations`.  but this PR doesn't modify the code in bigbird_pegasus and I can't find the related imports etc. in bigbird_pegasus. 

Sure! Seems like you need to run `make style` and `make fix-copies`. 
If `make style` does not work, (meaning the tests for quality are still failing) then you have to do `pip install --upgrade -e ".[dev]". Basically to make sure that the `black` version you are using is the correct one

You also need to rebase on main ! 

Okay! Now fixing this should only need `make fixup`. But to make sure you have the correct black version run `pip install -e .` should do the trick. Once you are ready for a final review, feel free to ping @sgugger 

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.

sorry for the late update. will finish it this week. 

Hi @ArthurZucker , I updated the docstrings. As for the fast function, I explained why it couldn't be replaced with `np.random.randint` in [this reply](https://github.com/huggingface/transformers/pull/21499#discussion_r1154818120). Could you double-check it? 

Sorry for the delay, went in holidays. This seems like a big modification, so I think having performance stats would be better before merging (this adds a layer of complexity which we are not usually big fans of)>

> Sorry for the delay, went in holidays. This seems like a big modification, so I think having performance stats would be better before merging (this adds a layer of complexity which we are not usually big fans of)>

Hi @ArthurZucker, thanks for your comments! I agree that a big project like huggingface should have high code quality requirements! no worries. 

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.