Experimental changes to the pyglet clock

[Leif Theden]

Greetings!  In response to a conversation in another thread, I've put together some changes to the pyglet Clock that offer some performance benefits between 25% - 80% during use based on my benchmarks.  This clock doesn't change the API or behavior of the Clock and is a 'drop in replacement'.

Here's the other thread:
https://groups.google.com/forum/#!topic/pyglet-users/59IfchOecRY

For this topic, I'll outline a couple terms and ideas.  For the purposes of this post:

• "clock" refers to the pyglet Clock class.
• "event" means something that has been scheduled
  
• "interval" and "delayed" events, scheduled with Clock.schedule_once, Clock.schedule_interval, and Clock.schedule_interval_soft are impacted
• "every tick" items, scheduled with Clock.schedule are unaffected
• When I mention "scheduled events", I will be referring to delayed and interval events, not "every tick" events
• "soft scheduling" is a mechanism pyglet uses to distribute interval events over time without executing them all at once, even if they were scheduled at the same time
  

The purpose of changing the implementation of the Clock was motivated by using cProfile to research bottlenecks with pyglet.  I noticed that list sorting was impacting performance, and set out to create a replacement heap-based clock.  While it may be difficult to notice any gains from the changes in use, it may make pyglet more suitable for using many more scheduled events than was previously available.  Just from my own experimentation, significant gains come from scheduling over 200 events.

The current Clock maintains a list of events that are to be executed in sorted order.  The overhead for maintaining sorted order can be quite high, especially if there are several 100's of events or a lot of scheduling/unscheduling going on.  This heap-based clock implementation offers much faster scheduling and unscheduling of interval & delayed events because it don't sort the list.  Events that execute each frame/tick are unaffected.

The only drawback from this heap clock is that 'soft scheduling' is impacted.  By my benchmarks, it typically executes at the same speed or slower as the sorted-list Clock (the one in use now).  Soft-scheduling requires a sorted list of events to correctly find a free spot in the schedule so that several events do not overlap and create usage spikes, so the heap-clock has to create a sorted copy of the event queue.  Perhaps another mechanism for soft scheduling can be used, however, I have not investigated alternative methods.

Even though soft scheduling is impacted, I believe that it is not used often enough in the real world to create a situation where it will negatively affect gains made in other parts of Clock.  The changes have been tested against the standard test suite, and I've used a few pyglet apps/games and they seemed to run fine, so I don't see any major issues.  I invite anyone to check out the changes and play with it.

In summary:

• + faster scheduling and unscheduling of events
• + faster processing of scheduled events
• - slower soft scheduling of events

For anyone interested, here is a link to my bitbucket repo with the clock changes:
https://bitbucket.org/leif_theden/pyglet/branch/heap_clock

Thank you!

[Leif Theden]

Direct links to source:

https://bitbucket.org/leif_theden/pyglet/src/be965fbe37512a2bc207990f9a148f12942733a2/pyglet/clock.py?at=heap_clock
https://bitbucket.org/leif_theden/pyglet/src/be965fbe37512a2bc207990f9a148f12942733a2/tests/unit/test_clock.py?at=heap_clock

[Petr Viktorin]

On Sat, Oct 24, 2015 at 11:39 PM, Leif Theden <leif....@gmail.com> wrote:
> Greetings! In response to a conversation in another thread, I've put
> together some changes to the pyglet Clock that offer some performance
> benefits between 25% - 80% during use based on my benchmarks. This clock
> doesn't change the API or behavior of the Clock and is a 'drop in
> replacement'.
>

[...]

>
> The only drawback from this heap clock is that 'soft scheduling' is
> impacted. By my benchmarks, it typically executes at the same speed or
> slower as the sorted-list Clock (the one in use now). Soft-scheduling
> requires a sorted list of events to correctly find a free spot in the
> schedule so that several events do not overlap and create usage spikes, so
> the heap-clock has to create a sorted copy of the event queue. Perhaps
> another mechanism for soft scheduling can be used, however, I have not
> investigated alternative methods.

Hello,
I haven't studied the code in detail, but I'd like to point out that:
1. Every sorted list is also a heap [0]
2. Python's sorting algorithm is very good at lists that are "almost"
sorted (i.e. a few elements/subsequences out of place) [1]

So, for soft scheduling you might want to sort the list, insert the
event, and then leave the list sorted. This would make the next soft
schedule faster, as long as intervening heapq operations don't shuffle
the list *completely*.

I think it'd be worth exploring but haven't tested/benchmarked it myself.


[0] https://docs.python.org/3/library/heapq.html : "heap.sort()
maintains the heap invariant!"
[1] https://hg.python.org/cpython/file/3.5/Objects/listsort.txt :
"3sort", "%sort"

[Benjamin Moran]

Nice work! I'll give this a try on some apps and see how it goes.

[Salvakiya]

I do believe this is exactly what I need. Why is it not standard?

[Leif Theden]

Great suggestion, Petr.  I made the changes that you suggested, and got a 8-10% speed increase for my synthetic benchmarks.  Salvakiya, I'm not sure why a heap based scheduler was used in the past.  Perhaps the benefit was never thought to be good enough to justify rewriting the existing scheduler.  This change that I'm proposing is just an incremental boost, not really one that is drastic.  A 40% increase in performance in the scheduler doesn't mean much if the scheduler is 10% of the overall CPU use.  Anyway, I'll need to do more benchmarks to see how it goes with real-world use.

So... don't get your hopes up too much about fixing performance issues.  Pyglet's bottlenecks are still graphics related, and will take care to make a quick program.

I've updated my branch.

[Benjamin Moran]

Tested on a Linux box with Python 3.5. No issues. I'll give it another try with your recent update.

It may be a relatively small improvement, but many small improvements add up!


2015年10月26日月曜日 11時51分43秒 UTC+9 Leif Theden:

[Salvakiya]

I think the issue with the scheduler I had was with animations. I had something like 200+animations in my benchmark and they took down the fps badly.

[Rob]

If the new clock works fine, we can probably pull it into the main branch for 1.3.x. So make a pull request when you feel you are ready.

I did know you already did improvements in your fork. Just did not have time yet to pull those in.

Rob

Op maandag 26 oktober 2015 05:09:50 UTC+1 schreef Benjamin Moran:

[Benjamin Moran]

Sorry to bump up this thread after all of this time, but I was curious if there were any issues with getting this merged.

[Rob van der Most]

I almost forgot about this. Added it to the roadmap of 1.3: https://bitbucket.org/pyglet/pyglet/wiki/Roadmap

Rob

--
You received this message because you are subscribed to the Google Groups "pyglet-users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pyglet-users...@googlegroups.com.
To post to this group, send email to pyglet...@googlegroups.com.

Visit this group at https://groups.google.com/group/pyglet-users.

For more options, visit https://groups.google.com/d/optout.

[Benjamin Moran]

Great!  This was a nice bit of work Leif did, so I'm glad it won't be forgotten now.

[Benjamin Moran]

Hey guys,

I'm going to see about merging this in, sometime in the near future. It seems perfectly stable and functional, but it would be great to get some additional feedback if anyone can try it out.

-Ben

[Benjamin Moran]

 I've actually come across some issues myself, so this will need some additional work before merging.  The first is a fairly consistent crash when changing a sprite's animation. The second is that the animation speed is not consistent. It's off enough to be visually obvious, so it should be tweaked a bit.

[Leif Theden]

I wrote the experimental clock.  Thanks for the input.  I realize I've been silent for a long time, but with some details about the issues, I can work towards better compatibility.

Leif

On Mon, Feb 20, 2017 at 7:09 AM, Benjamin Moran <benmo...@gmail.com> wrote:

 I've actually come across some issues myself, so this will need some additional work before merging.  The first is a fairly consistent crash when changing a sprite's animation. The second is that the animation speed is not consistent. It's off enough to be visually obvious, so it should be tweaked a bit.

--
You received this message because you are subscribed to a topic in the Google Groups "pyglet-users" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/pyglet-users/_0eLxtKfUy4/unsubscribe.
To unsubscribe from this group and all its topics, send an email to pyglet-users+unsubscribe@googlegroups.com.

[Benjamin Moran]

Hey Leif,

Glad to see you back. I'd be happy to put together some example code that shows the crash. That one should hopefully be straightforward to fix.
The animation speed issue is maybe related to the ts rounding code. Basically what happens is that an animation plays slowly for a second or two, and then plays rapidly as if it were "catching up".

On Tuesday, February 21, 2017 at 1:25:11 AM UTC+9, Leif Theden wrote:

I wrote the experimental clock.  Thanks for the input.  I realize I've been silent for a long time, but with some details about the issues, I can work towards better compatibility.

Leif

On Mon, Feb 20, 2017 at 7:09 AM, Benjamin Moran <benmo...@gmail.com> wrote:

 I've actually come across some issues myself, so this will need some additional work before merging.  The first is a fairly consistent crash when changing a sprite's animation. The second is that the animation speed is not consistent. It's off enough to be visually obvious, so it should be tweaked a bit.

--
You received this message because you are subscribed to a topic in the Google Groups "pyglet-users" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/pyglet-users/_0eLxtKfUy4/unsubscribe.

To unsubscribe from this group and all its topics, send an email to pyglet-users...@googlegroups.com.

[Benjamin Moran]

Leif,

I put together a quick example. While it doesn't crash, It does illustrate what may be the root cause:  animations are not being unscheduled properly. When changing a sprite's img/animation, it will call clock.unschedule(). The print function in the example code shows that the list of scheduled functions keeps growing every time you change one. Hope this helps!

(It would be a lot cleaner to use a proper animation, but I just mocked this up using transforms of the included png in the pyglet repo)

import pyglet

window = pyglet.window.Window()
batch = pyglet.graphics.Batch()

image = pyglet.image.load("examples/pyglet.png")
image.anchor_x = image.width//2
image.anchor_y = image.height//2

frames = []
for i in range(4):
    angle = i * 90 % 360
    img = image.texture.get_transform(rotate=angle)
    frames.append(img)
ani = pyglet.image.Animation.from_image_sequence(frames, 0.08)
ani2 = pyglet.image.Animation.from_image_sequence(frames, 0.2)

sprite = pyglet.sprite.Sprite(ani, x=window.width//2, y=window.height//2, batch=batch)


@window.event
def on_key_press(key, mod):
    if key == pyglet.window.key.SPACE:
        sprite.image = ani2
        print(pyglet.clock.get_default()._schedule_interval_items)


@window.event
def on_draw():
    window.clear()
    batch.draw()


if __name__ == "__main__":
    pyglet.app.run()

On Tuesday, February 21, 2017 at 1:25:11 AM UTC+9, Leif Theden wrote:

I wrote the experimental clock.  Thanks for the input.  I realize I've been silent for a long time, but with some details about the issues, I can work towards better compatibility.

Leif

On Mon, Feb 20, 2017 at 7:09 AM, Benjamin Moran <benmo...@gmail.com> wrote:

 I've actually come across some issues myself, so this will need some additional work before merging.  The first is a fairly consistent crash when changing a sprite's animation. The second is that the animation speed is not consistent. It's off enough to be visually obvious, so it should be tweaked a bit.

--
You received this message because you are subscribed to a topic in the Google Groups "pyglet-users" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/pyglet-users/_0eLxtKfUy4/unsubscribe.

To unsubscribe from this group and all its topics, send an email to pyglet-users...@googlegroups.com.

[Leif Theden]

Thank you brad for the detailed comments and the test code.  I was able to isolate the problem to the "is" operator not properly identifying bound methods of sprite objects (likely, or any other bound method for that matter).  Because it was not properly id'ing function passed to Clock.unschedule, they were not being removed.  It seems that "is" will not work, but a simple equality check will.  Unit tests seem to work well.

You'll notice that your test code will still report 2 scheduled items in the queue.  Note the comments in the unschedule method; items are not removed right away in the event that there are several unscheduled functions at once and causing excessive heap activity.  They remain in the queue until they are checked again then removed without processing callbacks.

[Benjamin Moran]

That did the trick!
I think we've all been bitten by "is" vs "==" before, so that's great it was an easy fix.

I'm also happy to report that this also fixes the unstable animation speed issue. As it turns out, the animation speed was always fine. What I was seeing was multiple animations being added on top of one another, and running in parallel interleaved.

Now that this is fixed, shall we merge it in?

[Benjamin Moran]

Hi Leif,

Sorry to pester, but do you have any issues with merging this in? I can do it of you're short on time.

[Leif Theden]

No worries Benjamin. Let me look over it today and think about compatibility. I think I covered all of the major functionality when I wrote it, but that was over a year ago. I'll let you know this week.

On Mon, Apr 3, 2017 at 7:12 AM Benjamin Moran <benmo...@gmail.com> wrote:

Hi Leif,

Sorry to pester, but do you have any issues with merging this in? I can do it of you're short on time.

[Benjamin Moran]

Thanks Leif. It would be great to get this bit of code into the next release. If you see anything that you've missed, I'm available to help if necessary.

[Leif Theden]

I ran through the test suite again (passed) and can't think of any other tests for it ATM.  I don't see a problem merging it.

[Benjamin Moran]

Great. I went ahead and manually commited it. It's a bit of a change from the previous implementation, but it's a nice upgrade and fundamentally solid. Now that it's in, we can see if anyone finds any edge cases. I've been using it in a few test projects already, without issues (other than the ones you fixed already :))

Thanks Leif