IndexError: index 1000 is out of bounds for dimension 0 with size 1000

[psychedelicious]

Describe your environment

• GPU: mps
• VRAM: 32GB unified memory
• CPU arch: arm64
• OS: macOS
• Python: mamba
• Branch: my ui dev branch based on this development branch, no changes made to this repo's code
• Commit: psychedelicious@5cf11bd

Edit: Issue also present on main: 751283a

Describe the bug
Encountered while testing web UI, reproducible in dream.py and current web UI.

Exception in thread Thread-17 (_handle_event_internal):
Traceback (most recent call last):
  File "/opt/homebrew/Caskroom/mambaforge/base/envs/ldm/lib/python3.10/threading.py", line 1016, in _bootstrap_inner
    self.run()
  File "/opt/homebrew/Caskroom/mambaforge/base/envs/ldm/lib/python3.10/threading.py", line 953, in run
    self._target(*self._args, **self._kwargs)
  File "/opt/homebrew/Caskroom/mambaforge/base/envs/ldm/lib/python3.10/site-packages/socketio/server.py", line 730, in _handle_event_internal
    r = server._trigger_event(data[0], namespace, sid, *data[1:])
  File "/opt/homebrew/Caskroom/mambaforge/base/envs/ldm/lib/python3.10/site-packages/socketio/server.py", line 755, in _trigger_event
    return self.handlers[namespace][event](*args)
  File "/opt/homebrew/Caskroom/mambaforge/base/envs/ldm/lib/python3.10/site-packages/flask_socketio/__init__.py", line 282, in _handler
    return self._handle_event(handler, message, namespace, sid,
  File "/opt/homebrew/Caskroom/mambaforge/base/envs/ldm/lib/python3.10/site-packages/flask_socketio/__init__.py", line 826, in _handle_event
    ret = handler(*args)
  File "/Users/spencer/Documents/Code/fork-stable-diffusion/backend/server.py", line 96, in handle_generate_image
    generate_image(data)
  File "/Users/spencer/Documents/Code/fork-stable-diffusion/backend/server.py", line 167, in generate_image
    t2i.prompt2image(prompt,
  File "/Users/spencer/Documents/Code/fork-stable-diffusion/ldm/generate.py", line 323, in prompt2image
    results = generator.generate(
  File "/Users/spencer/Documents/Code/fork-stable-diffusion/ldm/dream/generator/base.py", line 42, in generate
    make_image          = self.get_make_image(
  File "/opt/homebrew/Caskroom/mambaforge/base/envs/ldm/lib/python3.10/site-packages/torch/autograd/grad_mode.py", line 27, in decorate_context
    return func(*args, **kwargs)
  File "/Users/spencer/Documents/Code/fork-stable-diffusion/ldm/dream/generator/img2img.py", line 31, in get_make_image
    sampler.make_schedule(
  File "/Users/spencer/Documents/Code/fork-stable-diffusion/ldm/models/diffusion/ddim.py", line 87, in make_schedule
    ) = make_ddim_sampling_parameters(
  File "/Users/spencer/Documents/Code/fork-stable-diffusion/ldm/modules/diffusionmodules/util.py", line 94, in make_ddim_sampling_parameters
    alphas = alphacums[ddim_timesteps]
IndexError: index 1000 is out of bounds for dimension 0 with size 1000

To Reproduce
Interestingly, this seems to happen whenever an init image is used with steps = 27, regardless of other parameters. Tested many. Tried in my web UI, dream.py and the current web UI, all fail with same error.

The parameters I used when first encountering the error, for completeness' sake, formatted for dream.py CLI: Futuristic town on the moon with pedestrian walking by -s 27 -H 512 -W 512 -A k_euler -f 0.75 -I outputs/img-samples/000007.-1.png

Init img:

[lstein]

I can reproduce this bug. It only happens when there is an init image. No dependency on the strength, which is weird, since the actual number of steps is computed as strength*steps.

The bug is in the ddim sampler.

[psychedelicious]

Whew, so unrelated to system architecture. Was worried it was an M1 issue.

Is this an upstream issue?

[Any-Winter-4079]

For 512x512, in my M1.
-s 27 fails (also)
-s 99 works
-s 100 works
-s 101 fails
-s 108 fails
-s 110 fails
-s 120 works
-s 130 works
-s 150 works
-s 153 works
-s 160 works
-s 163 works
-s 164 works
Don't see the logic so far.

[Any-Winter-4079]

So everything between -s 101 and -s 111 fails (both included)

[n00mkrad]

This is limited to DDIM btw

[Any-Winter-4079]

@lstein Okay, here's what I've found.
Add
print(self.ddim_timesteps)
right after

self.ddim_timesteps = make_ddim_timesteps(
            ddim_discr_method=ddim_discretize,
            num_ddim_timesteps=ddim_num_steps,
            num_ddpm_timesteps=self.ddpm_num_timesteps,
            verbose=verbose,
        )

in ldm/models/diffusion/ddim.py

It will print the timesteps. Now let's take -s 27 (fails)

[   1   38   75  112  149  186  223  260  297  334  371  408  445  482
  519  556  593  630  667  704  741  778  815  852  889  926  963 1000]

You can see 1000, which aligns with the error
IndexError: index 1000 is out of bounds for dimension 0 with size 1000

Now let's take -s 28 (works)

[  1  36  71 106 141 176 211 246 281 316 351 386 421 456 491 526 561 596
 631 666 701 736 771 806 841 876 911 946 981]

As you can see, no 1000.
So we need to make sure 1000 is not returned (or modify it after it returns and replace 1000 w/ 999)

The calculation to return the steps is made in ldm/modules/diffusionmodules/util.py in function make_ddim_timesteps

[Any-Winter-4079]

@lstein In particular, this bug can be fixed by simply changing
line 85 of ldm/modules/diffusionmodules/util.py

- steps_out = ddim_timesteps + 1
+ steps_out = np.where(ddim_timesteps != 999, ddim_timesteps+1, ddim_timesteps)

I'm not sure what side-effects this may have, but at first sight it shouldn't matter much, 1000 vs 999.

[lstein]

Does anyone understand why 1000 is cursed?

[lstein]

@lstein In particular, this bug can be fixed by simply changing line 85 of ldm/modules/diffusionmodules/util.py

- steps_out = ddim_timesteps + 1
+ steps_out = np.where(ddim_timesteps != 999, ddim_timesteps+1, ddim_timesteps)

I'm not sure what side-effects this may have, but at first sight it shouldn't matter much, 1000 vs 999.

This fix doesn't actually work. Instead I tried:

- steps_out = ddim_timesteps + 1
+ steps_out = ddim_timesteps

This seems to work without side effects. Would you mind testing it a bit? This is in a section of code I don't understand at all.

[Any-Winter-4079]

@lstein Okay, so a few comments and findings.

Interestingly, this seems to happen whenever an init image is used with steps = 27, regardless of other parameters. Tested many. Tried in my web UI, dream.py and the current web UI, all fail with same error.

It isn't specific to using init images. I've tested
dream> Futuristic town on the moon with pedestrian walking by -m ddim -s 27
and it fails the same.

Now, the conflictive function (in ldm/modules/diffusionmodules/util.py) has 3 important arguments

def make_ddim_timesteps(
    ddim_discr_method, num_ddim_timesteps, num_ddpm_timesteps, verbose=True
)

1. ddim_discr_method is either 'uniform' or 'quad'. It tells how to separate values. For example, in 'uniform', values are uniformly separated. For
   [ 1 38 75 112 149 186 223 260 297 334 371 408 445 482
   519 556 593 630 667 704 741 778 815 852 889 926 963 1000]
   Notice how element n + 1 = element n + 37.
   Conversely, here's an example of 'quad'
   [ 1 2 5 11 19 30 43 58 76 96 119 144 171 201 232 267 303 343
   384 428 474 522 573 627 682 740 801]

2. num_ddim_timesteps are the steps you specify. So, -s 27 will make num_ddim_timesteps = 27

3. num_ddpm_timesteps is set to 1000 by default. Its value comes from ldm/models/diffusion/ddim.py

num_ddpm_timesteps=self.ddpm_num_timesteps,
where
self.ddpm_num_timesteps = model.num_timesteps
so this 1000 comes from the model itself.
The model is taken from
self.model = model
which is passed as an argument when instantiating a DDIM object
def __init__(self, model, schedule='linear', device=None, **kwargs)
Now, I know there's a bunch of config.yaml files with timesteps: 1000, but at this point I get a bit lost with so many files and it's not obvious to me if any of those could modify the value, or its unintended consequences.

Okay, back to our function.

def make_ddim_timesteps(
    ddim_discr_method, num_ddim_timesteps, num_ddpm_timesteps, verbose=True
)

Basically, we calculate c from num_ddpm_timesteps (1000) and the steps you specify (let's say 27).
c = num_ddpm_timesteps // num_ddim_timesteps
In this case, the integer division is 1000 // 27 = 37.
So this is the 37 that is used when I said element n + 1 = element n + 37.

Now, up to this point everything makes sense.
This is used to uniformly separate the values, starting at 0 (inclusive) up to 1000 (exclusive), with a stride of 37.
ddim_timesteps = np.asarray(list(range(0, num_ddpm_timesteps, c)))
which gives us
[ 0 37 74 111 148 185 222 259 296 333 370 407 444 481 518 555 592 629
666 703 740 777 814 851 888 925 962 999]

Now, the original code from CompVis says

# add one to get the final alpha values right (the ones from first scale to data during sampling)
steps_out = ddim_timesteps + 1

I am not sure I understand what they mean, but it seems they purposefully want to +1 to every value. So we eventually get
[ 1 38 75 112 149 186 223 260 297 334 371 408 445 482
519 556 593 630 667 704 741 778 815 852 889 926 963 1000]
That obviously creates a problem, because they have
alphas = alphacums[ddim_timesteps] which goes down its own rabbit hole, but the gist is, index 1000 is out of bounds.

Now, as a fix, we can either modify all values with

- steps_out = ddim_timesteps + 1
+ steps_out = ddim_timesteps

and use
[ 0 37 74 111 148 185 222 259 296 333 370 407 444 481 518 555 592 629
666 703 740 777 814 851 888 925 962 999]
or we can try to preserve their +1 computation for all -s (steps) that don't generate a 999 (for example, -s 100 has its last value as 990, which is then transformed into 991). And, for the rare cases where the last value is 999, we can keep that value at 999.
[ 1 38 75 112 149 186 223 260 297 334 371 408 445 482
519 556 593 630 667 704 741 778 815 852 889 926 963 999*]
So we keep the +1 for all values, still with a stride of 37, except for the last one, with a stride of 36.

I've tried both methods and I don't see any differences at first sight. Left is removing +1 for all. Right is +1 for all except if already 999.

dream> Futuristic town on the moon with pedestrian walking by -m ddim -s 27 -S 817924315

By the way, I don't know why
steps_out = np.where(ddim_timesteps != 999, ddim_timesteps+1, ddim_timesteps) doesn't work for you
It basically takes the array (ddim_timesteps) and adds 1 to every value if the condition != 999 is met. See docs:
https://numpy.org/doc/stable/reference/generated/numpy.where.html
Works perfect on my end. Maybe it's a numpy version thing?

Anyway, that's what I've learnt after some digging.

[psychedelicious]

@Any-Winter-4079 Nice work. I used imgdiff to compare the images and it says they are equal - pixel data is identical.