Re: [pygame] Dirty rect overlapping optimizations

[Greg Ewing]

Ian Mallett wrote:
​I mean this in a fundamental, mathematical sense. With O(n) rectangles, 
you can produce O(n^2) regions that cannot be decomposed into fewer than 
O(n^2) disjoint rectangles.


True, but that's a worst case, unlikely to be approached in practice.

Also, for this application, there will be some minimum size of
rectangle below which the overhead of decomposing it further would
be a net loss. If you stop at that point, there will be an upper
bound on the number of rectangles you're dealing with.

--
Greg

Re: [pygame] Dirty rect overlapping optimizations

[Ian Mallett]

On Mon, Mar 27, 2017 at 5:26 PM, Greg Ewing 
wrote:

> Ian Mallett wrote:
>
>> Unfortunately, computing those rectangles is annoying, and also O(n^2) in
>> the number of rectangles
>>
>
> With the right data structures and algorithms, it doesn't have to be.
>

​I mean this in a fundamental, mathematical sense. With O(n) rectangles,
you can produce O(n^2) regions that cannot be decomposed into fewer than
O(n^2) disjoint rectangles.

Ian​

Re: [pygame] Dirty rect overlapping optimizations

[Greg Ewing]

Ian Mallett wrote:
Unfortunately, computing those rectangles is annoying, and 
also O(n^2) in the number of rectangles


With the right data structures and algorithms, it doesn't have to be.
Apple's Quickdraw had some very efficient ways of representing and
operating on regions made up of collections of rectangles.

There's some info and further pointers about it here:

http://basalgangster.macgui.com/RetroMacComputing/The_Long_View/Entries/2010/8/29_Regions.html

--
Greg

Re: [pygame] Dirty rect overlapping optimizations

[Ian Mallett]

On Mon, Mar 27, 2017 at 12:34 PM, René Dudfield  wrote:

> On Mon, Mar 27, 2017 at 8:08 PM, Ian Mallett  wrote:
>
>> --IDK if pygame does this, but I expect blitting, with overdraw, to a
>> fullscreen temporary surface, and then sending the whole surface every
>> frame to the GPU would be faster than updating multiple smaller portions of
>> the GPU memory with CPU data.
>>
>
> Double buffering works like that. Except with update you can tell it to
> update only parts of the back buffer. When you display.flip()/update() it
> sends the data. It's faster because less data is sent over the bus. But
> even on OpenGL slower implementations (or with higher resolutions) you can
> gain benefits by only updating part of the buffer(s). Not on monster
> dedicated cards at lower resolutions of course.
>

​I suppose. Still, this should be asynchronous. Maybe making it work in
Python isn't possible.​

--IIRC the fastest algorithm for rect-rect collision detection is the
>> max-of-mins/min-of-maxes method, which is widely known. It maps nicely to
>> SSE too.
>>
>
> Sounds interesting. Maybe that's what we're using now for rect
> collision... I'm not sure of the algo name. It's only in C however.
>

​Yeah I'm not sure it has its own name. And definitely you'd want it in C
or equivalent.​


> Below is one of the cases that benefits the most. (actually after drawing
> this I'm not sure if this is actually true or I dreamed it up... but I drew
> the diagrams... so it feels a waste to delete them).
>
> Currently the update method combines two rects like this:
> ___
> | |
> |   __|
> |___|_|   |
> | |
> | |
> |_|
>
> Into a big rect like this:
> ___
> | |
> | |
> |   XX| # - updated, but no need.
> |###  | X - over drawn.
> |###  |
> |###__|
>
>
> Note in these crude diagrams the # area is drawn even though it doesn't
> need to be, and the XX is over draw. When there are some overlapping rects
> like this that are large, that can be quite a saving of pixels not needed
> to be drawn.
>

​Right.

the thing to consider is what you do about it. You can't just "not draw"
those pixels, because you still have to iterate over them, which defeats
the point. Instead, you have to decompose the combination of rects into
disjoint subrects that span the region that needs to be updated. For your
example:

┌┐
││
│  ┌─┼──┐
└──┼─┘  │
   ││
   └┘

. . . the decomposition could be something like:

┌┐
││
│├──┐
└──┬─┤  │
   │ │  │
   └─┴──┘

The key point is that doing this decomposition needs to be faster than just
drawing. Unfortunately, computing those rectangles is annoying, and also
O(n^2) in the number of rectangles (whereas the number of overdrawn pixels
you save can be linear-ish).

Ian​

Re: [pygame] github terms of service issues

[Daniel Foerster]

On Mar 27, 2017 08:41, "Dominik George"  wrote:


The first issue is children under the age of 13 years not being allowed
to register with GitHub. This issue already existed before GitHub
updated their ToS, and they claim it is because of COPPA. I do think
that they could easily fix this by not requiring a legal name, which is
the only data thewy colelct that falls under COPPA, but they don't
listen. Then, COPPA only "protects" US children, and GitHub are, in my
opinion, wrong in putting this age restriction in their ToS explicitly.
They could simply tell users "you need to be legally able to accept our
privacy terms". This would mean that in the US, the restrictions by
COPPA would apply, and in e.g. Germany, a child aged seven and above
could register given parental consent. I had a lengthy discussion about
that with GitHub Legal, but with no result.


I'm almost completely certain that the COPPA applies to websites in the US
regardless of the location of the website user.


Now you might wonder whether contributors younger than 13 years do
matter at all. Please note that this is primarily opinion-based - this
aspect of my criticism is therefore explicitly opinionated. I *do* think
that excluding a certain age group is plain discrimination against a
subgroup of people. Furthermore, I have seen children as young as nine
or ten years contribute to free software, both with bug reports and with
actual code patches. This is something that is not widely seen, as
Teckids is the only organisation (according to people at international
conferences) actually helping young users to become *active* members of
the community, but it does exist and I am strongly against adding
hurdles to it.


I'd suggest looking at some of the things StackOverflow has suggested on
this topic; for example, having parents set up an account and then "giving"
it to the child at the legal point in time.

A quite
good analysis of that can be found here
https://www.mirbsd.org/permalinks/wlog-10_e20170301-tg.htm and here
https://joeyh.name/blog/entry/what_I_would_ask_my_lawyers_
about_the_new_Github_TOS/
.

I have spoken to two lawyers about that, and they basically say that on
first glance, the ToS are indeed very problematic.

The FSF, in the meantime, has published a post stating that the new ToS
do not conflict with the GPL license family here
https://www.fsf.org/blogs/licensing/do-githubs-updated-
terms-of-service-conflict-with-copyleft
(but they still discourage use of GitHub), I (and others) do not think
their view is correct, because the ToS explicitly say that they may use
works without attribution, and the GPL licenses explicitly require
copies to carry attribution. Also, even if the FSF is correct, this only
applies to GPL, and probably not to CC-BY-SA and other licenses
requiring attribution, or even prohibiting sub-licensing under other
licenses.


The problem with this is that actual lawyers in the field have pointed out
that these non-legal articles are almost certainly completely baseless.
Saying that you think the FSF is wrong seems a bit presumptuous seeing
they're paid to be able to understand this sort of law.


In any case, with GitHub imposing  terms on a license granted to
them, all contributors also need to grant this license, for past *and*
new contributions. *If* the separate terms do not conflict with GPL,
this might be a non-issue for GPL code, but it might be an issue with
other licenses. As I see that, in order to merge code into the
repository hosted on GitHub from an outside contributor would require
them to expclicitly grant a license as required by the GitHub ToS, or
even accept the ToS even if they do not register with GitHub.


I'd suggest looking at the HackerNews discussion of the mirbsd.org article
if you have not already; there's no change in rights to the code beyond
what is already provided by uploading code to the publicly accessible
internet.

Re: [pygame] Dirty rect overlapping optimizations

[René Dudfield]

On Mon, Mar 27, 2017 at 8:08 PM, Ian Mallett  wrote:

> Hi,
>
> Just a couple quick, miscellaneous notes on this problem:
>
> --IDK if pygame does this, but I expect blitting, with overdraw, to a
> fullscreen temporary surface, and then sending the whole surface every
> frame to the GPU would be faster than updating multiple smaller portions of
> the GPU memory with CPU data.
>
>
Double buffering works like that. Except with update you can tell it to
update only parts of the back buffer. When you display.flip()/update() it
sends the data. It's faster because less data is sent over the bus. But
even on OpenGL slower implementations (or with higher resolutions) you can
gain benefits by only updating part of the buffer(s). Not on monster
dedicated cards at lower resolutions of course.


> --Dirty rects were never really a performance issue for me. This is partly
> because I usually implement the scheme above, more-or-less, partly because
> I avoid it algorithmically, and partly because blitting is inexpensive and
> typical overdraw rates are low (as they would be in a good GPU renderer
> too).
>
> --IIRC the fastest algorithm for rect-rect collision detection is the
> max-of-mins/min-of-maxes method, which is widely known. It maps nicely to
> SSE too.
>
>
Sounds interesting. Maybe that's what we're using now for rect collision...
I'm not sure of the algo name. It's only in C however.



Below is one of the cases that benefits the most. (actually after drawing
this I'm not sure if this is actually true or I dreamed it up... but I drew
the diagrams... so it feels a waste to delete them).

Currently the update method combines two rects like this:
___
| |
|   __|
|___|_|   |
| |
| |
|_|

Into a big rect like this:
___
| |
| |
|   XX| # - updated, but no need.
|###  | X - over drawn.
|###  |
|###__|


Note in these crude diagrams the # area is drawn even though it doesn't
need to be, and the XX is over draw. When there are some overlapping rects
like this that are large, that can be quite a saving of pixels not needed
to be drawn.

Re: [pygame] Dirty rect overlapping optimizations

[Ian Mallett]

Hi,

On Mon, Mar 27, 2017 at 12:16 PM, DR0ID  wrote:

> On 27.03.2017 20:08, Ian Mallett wrote:
>
>> max-of-mins/min-of-maxes method
>>
>
> Hi Ian
>
> Could you share more about this method? Seems I can't find something
> related to dirty rects with that.
>
>
> ~DR0ID
>

It's a rect-rect collision detection algorithm, which could be applied to
detect which rects overlap (and gives the overlapping rect also). It's the
standard algorithm people use for this purpose, although people tend to
think of it in terms of multiple tests, which is less intuitive (to me,
anyway) and slower.

The test is basically (from memory):

collided = max(rect1.min,rect2.min) < min(rect1.max,rect2.max)


In 1D, you can think of "rect.min" as being "rect.left" and "rect.max"
being "rect.right". In nD rect.min is a vector [left,bottom,back,...] and
rect.max is a vector [right,top,front,...] and the "<" must apply along all
axes. That's why it's great for SSE. You can also subtract the terms to get
the dimensions of the overlapping area.

On Mon, Mar 27, 2017 at 12:23 PM, Radomir Dopieralski 
 wrote:

> On Mon, 27 Mar 2017 12:08:10 -0600
> Ian Mallett  wrote:
>
> > --There are two key cases to think about: (1) You have 1x1 pixel
> > rects for each pixel on the screen. No overdraw, so the algorithm is
> > complete waste.
>
> I think it would make sense to merge dirty rectangles even if they don't
> actually overlap, but simply touch. This would improve this use case
> (and a common use case of a tiled map) greatly.
>
> --
> Radomir Dopieralski
>

​I agree; this is desirable.​

Ian​

Re: [pygame] Dirty rect overlapping optimizations

[Radomir Dopieralski]

On Mon, 27 Mar 2017 12:08:10 -0600
Ian Mallett  wrote:

> --There are two key cases to think about: (1) You have 1x1 pixel
> rects for each pixel on the screen. No overdraw, so the algorithm is
> complete waste.

I think it would make sense to merge dirty rectangles even if they don't
actually overlap, but simply touch. This would improve this use case
(and a common use case of a tiled map) greatly.

-- 
Radomir Dopieralski

Re: [pygame] Dirty rect overlapping optimizations

[DR0ID]

On 27.03.2017 20:08, Ian Mallett wrote:

max-of-mins/min-of-maxes method


Hi Ian

Could you share more about this method? Seems I can't find something 
related to dirty rects with that.



~DR0ID

Re: [pygame] Dirty rect overlapping optimizations

[Ian Mallett]

Hi,

Just a couple quick, miscellaneous notes on this problem:

--IDK if pygame does this, but I expect blitting, with overdraw, to a
fullscreen temporary surface, and then sending the whole surface every
frame to the GPU would be faster than updating multiple smaller portions of
the GPU memory with CPU data.

--Dirty rects were never really a performance issue for me. This is partly
because I usually implement the scheme above, more-or-less, partly because
I avoid it algorithmically, and partly because blitting is inexpensive and
typical overdraw rates are low (as they would be in a good GPU renderer
too).

--IIRC the fastest algorithm for rect-rect collision detection is the
max-of-mins/min-of-maxes method, which is widely known. It maps nicely to
SSE too.

--I don't doubt there's no clear performance gain for current
implementations, especially if the algorithm is in Python.

--There are two key cases to think about: (1) You have 1x1 pixel rects for
each pixel on the screen. No overdraw, so the algorithm is complete waste.
(2) You have a bunch of fullscreen rects that of course all overlap 100%.

Ian

Re: [pygame] github terms of service issues

[René Dudfield]

Well, we're using launchpad already. We use it for building, and for making
PPAs available. We'll keep using it for those reasons I think.

(speaking of which, we should link those PPAs on the new GettingStarted
page).

I hadn't considered moving everything there. They do support git now. But I
guess there's less people using it than even bitbucket. I don't think they
have windows/OSX build support, so we'd need to use github with
travis/appveyor anyway for those.


cheers,



On Mon, Mar 27, 2017 at 3:38 PM, Sam Bull  wrote:

> On Mon, 2017-03-27 at 15:21 +0200, Jorge wrote:
> > Am 27.03.2017 um 11:59 schrieb Sam Bull:
> > > On Mon, 2017-03-27 at 11:24 +0200, Dominik George wrote:
> > > > > I use the tosdr.org plugin, which gives a rating for ToS for a
> > > > > website,
> > > > > and summarises the points of the license. Might give you a good
> > > > > overview, you can view the summary they give here:
> > > > >
> > > > > https://tosdr.org/#github
> > > > Unfortunately, the analysis provided there discusses the old ToS,
> > > > not
> > > > those in effect since February.
> > > Ah, reported to them that it is out-of-date. Looks like you could
> > > contribute some new points directly at https://edit.tosdr.org/ if
> > > you
> > > feel so inclined.
> > Have you considered NotABug or GitLab?
>
> Well, if we're mentioning alternatives, I've still yet to see anything
> with a better user experience than Launchpad, which is free for open
> source projects, and is open source itself. I still put all my projects
> up there.

Re: [pygame] github terms of service issues

[René Dudfield]

On Mon, Mar 27, 2017 at 3:21 PM, Jorge  wrote:

> Am 27.03.2017 um 11:59 schrieb Sam Bull:
>
> On Mon, 2017-03-27 at 11:24 +0200, Dominik George wrote:
>
> I use the tosdr.org plugin, which gives a rating for ToS for a
> website,
> and summarises the points of the license. Might give you a good
> overview, you can view the summary they give here:
> https://tosdr.org/#github
>
> Unfortunately, the analysis provided there discusses the old ToS, not
> those in effect since February.
>
> Ah, reported to them that it is out-of-date. Looks like you could
> contribute some new points directly at https://edit.tosdr.org/ if you
> feel so inclined.
>
> Have you considered NotABug  or GitLab
> ?
>

I haven't. Not sure about anyone else.

Re: [pygame] Dirty rect overlapping optimizations

[René Dudfield]

Cool about the blit function. Since the rect and surfaces are by reference,
then you only need to make sprite_image_list once (if you are blitting the
same thing every time). Additionally, I think it would likely be fast
enough for another commonly requested case (blit the same image to many
different spots). It would also work nicely for sprite groups. I think it's
worth some more API discussion, before merging it in. We'd also need some
tests and docs.


A couple of quick points.

   - hardware is slower sometimes (see raspberrypi link I posted). Not
   surprising for platforms like this where video memory is the same speed for
   CPUs and GPUs, and where there are 4 CPU cores that have a modern
   architecture.
   - memory reads are reduced a lot when you change the bitdepth from 4
   bytes to 1 or 2. On modern computers memory IO is always the bottleneck.
   Even with hardware acceleration, blitting less memory is faster. If you can
   use the same as the screen format (some bayer format) then it's often only
   8-12 bits of data per LCD pixel. YUV style formats are very fast, and lower
   memory because they are what movies use.
   - Run length encoded, even if not hardware accelerated, can be very
   quick because you read less memory.
   - You can't use memcpy for blit blends, format conversions, scaling etc.
   Memory alignment can be easy by just allocating an extra 32 or 16 byte of
   data, and having the start position be there. If you do this for each scan
   line, even better.
   - The current blit functions to screen can be problematic on some
   platforms with threads, since some platforms don't have thread safe display
   functions. Calling them outside the main thread is not possible (on some
   platforms). There are a few other parts which aren't exactly thread safe on
   SDL. A work around is to use multiple processes (1 per core is optimal) and
   use shared memory. That way there are no threading issues, and this is the
   most optimal way to do it anyway. You can create mmap'd Surfaces with
   frombuffer.
   - There are some multi threaded blit functions however floating around
   that use openmp. pgreloaded branches.
   - The jit blit functions can mostly gain speed advantages by taking
   advantage of platform optimal prefetch instructions, SIMD, but also CPU
   optimal stride (how much data to process in what sized chunk so it fits in
   the cache best). The best example of this is ANGLE, which has a very
   advanced run time assembler. (it has to to emulate OpenGL and dx in
   software!) But also numexpr does some of these optimizations.

Another software improvement would be using the new METH_FASTCALL on python
3.6+ Which can see 15%-30% improvements for cases like calling lots of
functions.
Anyway... I think there's lots of potential improvements for the
raspberrypi. Some of them will benefit both software and hardware renderers.


But I'm still interested in the dirty rect handling, for the naieve case.


cheers,


On Mon, Mar 27, 2017 at 4:59 PM, Leif Theden  wrote:

> I think a function that accepts a sequence of tuples in the form of
> (dest_surface, dest_position, source_area, blend_mode) would be enough.  It
> is only needed as a power-user optimization and I don't seem much value in
> watering it down or splitting it into multiple functions for beginners.  No
> need to overthink and complicate it.  Cython may help sprite rendering in
> Groups, but it would have to be implemented and tested.
>
> Has anyone considered releasing the GIL during blit operations?  Is it
> possible the release the GIL during a blit, then block when needed, in the
> cases of subsequent draw operations?  The optimized case would be to allow
> math operations to execute while the display buffer is being modified,
> while you are iterating over sprites.
>
> Here is my preliminary C code for a "blit_multi" function.  It is called
> "blit_list".  It only supports (dest_surface, dest_position) tuples, but it
> works as so far.
> https://gist.github.com/bitcraft/1785face7c5684916cde
>
> Use it like this:
>
> sprite_image_list = [(s.image, s.rect) for s in self.sprites]
> display.blit_list(sprite_image_list)
>
>
> Jitblit sounds interesting, but how is that different from just using
> Surface.convert() with the correct flags?  I may be mistaken here, but on
> all modern computers, using 32-bit surfaces can be optimized into a single
> memcpy call...bytealigned and whatnot.  No need to iterate over pixel data
> (RLE).  If that's the case, then it doesn't make sense to support legacy
> 8/16/24-bit image formats, and validates pygame_sdl2's position not to
> support them.
>
> I don't see a way to combat overdraw, except by informing users that it is
> happening.
>
> Anyway, all of this chatter is moot, if pygame moves to a hardware sprites
> soon.
>
> On Mon, Mar 27, 2017 at 6:18 AM, René Dudfield  wrote:
>
>> The use case is to speed up naieve drawing. With things like pygame zero,
>> where they update th

Re: [pygame] github terms of service issues

[René Dudfield]

Hi Nik,

thanks for the email. I think it's going to take some time to properly read
and digest all of that. For now I'll mainly reply to the pygame repo moving
to github, and the exclusion. (It would be nice to talk about other things
like German language needs on the website+docs, teaching resources, and
also the Debian things.)



I think this is worth taking up with the PSF, Raspberry PI, and also with
github.

Excluding people is not nice, and I think it's against what everyone wants.
(not sure about github, but I guess for them too). Perhaps with some more
voices asking for change they will come to a solution quicker.

Having said that, I think we're in a theoretical problem space with regards
to accepting patches for *pygame itself*. Whilst there have been, and are
people who could submit patches, none have. For example, there was a child
who co-authored a book about pygame with his dad. Then there was the
european digital girl of the year award winner who has made some pygame
programs. To mention only two people.

It's important for people wanting to participate in the python community,
and in digital culture at large. Excluding any person from that is not on
in my opinion.

To work around it, have you considered getting parents to to submit any
contributions they made? Of course this means children give the legal
rights to their parents. It would probably be a good lesson about free and
libre software in the process ;)

Luckily if they want to share any work they make with python, they can do
that on other websites (launchpad, bitbucket, and several hundreds of
others). I think this is a much more common case (100% in the last 17
years), that people want to make things with pygame, and python, and not
change python or pygame itself. So we are safe from that perspective - they
are not excluded from that.

However, that they are excluded from anything is not good.

If the FSF says it's compatible, I'm inclined to follow them since I don't
have the knowledge or resources to find out otherwise. But as you say the
GPL/LGPL is only one(two) of dozens of FLOSS licenses. Additionally, I
assume that the PSF also ok'd it, since they are on there now too.



The reasons for moving to github:

It's become very common in the python community. pygame has tiny resources,
and every hour we spend trying to explain bitbucket and hg for potential
collaborators is wasted effort. Managing issues is harder, CI integration
is harder, and even things like searching for source code via the web is
not there on bb.

The pygame_sdl2, and pygame_cffi projects are on github. These are other
pygame projects I'd like to collaborate with, and it makes it easier to do
so if we are in the same place. Tom, from pygame_sdl2 made some compelling
arguments on the usability of the interface compared to others. I've since
seen this in practice on other projects - it makes it easier to
collaborate. I was serious about it taking an hour or so of close attention
to teach people the basics of bitbucket and hg at sprints.  I could
basically work with one or two people and other people got stuck on things
and gave up. So the collaboration benefits are not theoretical - I've
witnessed them multiple times in practice, and have heard from others who
have had the same experience.

When people decide to use their very limited free time, they don't want to
learn a new website and version control system - they'd rather work on what
they are interested in. It's a big barrier to put in front of people.

CPython has moved their operations to github. Which means that pretty much
every single python developer has a github account to collaborate. Not only
that but out of the top 400 projects (by downloads) on pypi the vast
majority are on github. Most of the ones on bitbucket had a dual setup. I
did the analysis a few months ago. There's 7000+ pygame related repos on
github, and 400ish on bitbucket - even though pygame has been on bitbucket
for a long time. A large number of past contributors (pygame has been on
cvs, svn, hg, and now git) didn't have bitbucket accounts. Only one past
pygame repo contributor didn't have a github account (out of 50) and now
they do.

Finally, the pygame project has been on the verge of death for some years.
Anything we do to reduce maintenance effort, and make collaboration easier
the better. Actually I think pygame died, and some sort of zombie pygame is
walking around eating brains...  (well it would eat brains if it could get
that gamepad out of its mouth). I really do see strong evidence that moving
to github will allow more people to contribute, but also reduce the work
load for maintainers, such that pygame has more of a chance to exist.




I'm with you on this issue, and am happy to help raise it with the PSF and
Raspberry PI if you haven't already. It would be good to hear other peoples
opinions here, and especially from the PSF and Raspberry PI (who are both
on github and have policies of not excluding people).

Bu

Re: [pygame] Dirty rect overlapping optimizations

[Leif Theden]

I think a function that accepts a sequence of tuples in the form of
(dest_surface, dest_position, source_area, blend_mode) would be enough.  It
is only needed as a power-user optimization and I don't seem much value in
watering it down or splitting it into multiple functions for beginners.  No
need to overthink and complicate it.  Cython may help sprite rendering in
Groups, but it would have to be implemented and tested.

Has anyone considered releasing the GIL during blit operations?  Is it
possible the release the GIL during a blit, then block when needed, in the
cases of subsequent draw operations?  The optimized case would be to allow
math operations to execute while the display buffer is being modified,
while you are iterating over sprites.

Here is my preliminary C code for a "blit_multi" function.  It is called
"blit_list".  It only supports (dest_surface, dest_position) tuples, but it
works as so far.
https://gist.github.com/bitcraft/1785face7c5684916cde

Use it like this:

sprite_image_list = [(s.image, s.rect) for s in self.sprites]
display.blit_list(sprite_image_list)


Jitblit sounds interesting, but how is that different from just using
Surface.convert() with the correct flags?  I may be mistaken here, but on
all modern computers, using 32-bit surfaces can be optimized into a single
memcpy call...bytealigned and whatnot.  No need to iterate over pixel data
(RLE).  If that's the case, then it doesn't make sense to support legacy
8/16/24-bit image formats, and validates pygame_sdl2's position not to
support them.

I don't see a way to combat overdraw, except by informing users that it is
happening.

Anyway, all of this chatter is moot, if pygame moves to a hardware sprites
soon.

On Mon, Mar 27, 2017 at 6:18 AM, René Dudfield  wrote:

> The use case is to speed up naieve drawing. With things like pygame zero,
> where they update the whole screen no matter what you draw. Where if people
> just draw several images to the screen, we should be able to easily track
> their changes, and only update what has changed.
>
> Yeah! Batching APIs would be a useful additions indeed. Ones which do
> _multi things at once. The tricky bit is to finding a set of those
> functions which are useful for many cases. Also extending the API without
> adding a million different functions here and there. fill_multi, blit_multi
> etc. However, what does blit_multi do? Blit one surface to multiple places?
> What about blit blend arguments? What about sub rects? Shouldn't there be a
> batch API for blitting a lot of different surfaces to different rects at
> once? After all this you can see how the APIs could get complicated and the
> number of them large. We have drawline, and drawlines, do we have blit and
> blits?
>
> Relatedly, there is also a possibility of compiling the sprite classes in
> Cython. This may also give a decent speedup in some cases. As shown by
> things like psyco, and pypy speeding them up. They're loops in python after
> all. But I wonder if they can be compiled easily, or if they're too dynamic.
>
> Apart from the jit work going on using libjit, it would be useful to do
> data aware blits. What I mean by that is by looking at an image, you can
> find better ways to draw it. Eg. does the image only contain 6bits worth of
> colour? Then an RLE blit is the fastest, and using 32bit alpha transparency
> is wrong. Are there large areas of the same colour (which can be more
> quickly drawn with fill())? Can we split it into 5 surfaces (four on the
> edges, one in the middle) where only the edge surfaces are drawn with the
> much slower alpha transparency blitters? For many games, the images don't
> change, so this works quite well. However this would perhaps require quite
> an API change (not entirely sure of that), or could likely be implemented
> inside the sprite classes with some trickery.
>
> Another area is better memory alignment on a platform specific basis can
> give considerable gains. On the slower raspberry pi for example, 16 byte,
> and 32 byte aligned memory goes much faster. On many platforms this is 4
> bytes, or 8 bytes. Gains of around 600MB/s ->1300MB/s have been seen. This
> is one area where a libjit based blitter (or one like in ANGLE) can make
> significant improvements. This type of change only needs to happen where we
> allocate memory for surfaces (or maybe people have done that already).
>
> Finally, hardware support for things like jpeg drawing, and DMA are
> possibilities. For example, the raspberrypi has dedicated hardware for jpeg
> decoding (as does most hardware these days). This can be used to draw a
> jpeg from memory into a buffer, so if you are drawing photos onto the
> screen, then this is a very fast way to do it. However, this would require
> a more abstract Sprite class which loads files itself.
> Sprite('mybigphoto.jpg'). But interestingly (but not unexpectedly) the CPUs
> are outperforming the dedicated hardware, if you dedicate the CPUs to the
> task. Also for whe

Re: [pygame] github terms of service issues

[Dominik George]

Hi,

so, let me start with a introduction on my backgrounds and why I raised
criticism about the switch to GitHub. I am Nik, and more or less here in
two roles:

On the one hand, I am chairman of Teckids e.V., a German organisation
establishing the free software movement among children and students. As
part of our work, we use Python to teach coding to hundreds of children
every year, and PyGame is our core tool for that since our first tutor
(tutors at Teckids are children themselves) got into programming with
the excellent book Hello, World by Carter Sande. However, teaching
coding is only one aspect of our work - our most important goal (as
voted by our members last weekend) is improving free software to make it
suitable for educational use and use by children, and foster these
projects.

On the other hand, I am the current maintainer of PyGame in Debian
(starting only recently). My package version is not yet available,
because the upload was rejected due to copyright uncertainties
(unrelated to those discussed here). This is of course somewhat mixed
with the Teckids role as it is part of our efforts to make and keep free
software tools for children available.

So, the issues with GitHub are twofold as well. First of all, without
looking at the BitBucket ToS, I assume that the switch to GitHub
actually does not make the situation *worse* - this is something that
would need to be found out¹.

Please let me explain the two issues and how they relate.

The first issue is children under the age of 13 years not being allowed
to register with GitHub. This issue already existed before GitHub
updated their ToS, and they claim it is because of COPPA. I do think
that they could easily fix this by not requiring a legal name, which is
the only data thewy colelct that falls under COPPA, but they don't
listen. Then, COPPA only "protects" US children, and GitHub are, in my
opinion, wrong in putting this age restriction in their ToS explicitly.
They could simply tell users "you need to be legally able to accept our
privacy terms". This would mean that in the US, the restrictions by
COPPA would apply, and in e.g. Germany, a child aged seven and above
could register given parental consent. I had a lengthy discussion about
that with GitHub Legal, but with no result.

Now you might wonder whether contributors younger than 13 years do
matter at all. Please note that this is primarily opinion-based - this
aspect of my criticism is therefore explicitly opinionated. I *do* think
that excluding a certain age group is plain discrimination against a
subgroup of people. Furthermore, I have seen children as young as nine
or ten years contribute to free software, both with bug reports and with
actual code patches. This is something that is not widely seen, as
Teckids is the only organisation (according to people at international
conferences) actually helping young users to become *active* members of
the community, but it does exist and I am strongly against adding
hurdles to it.

I would personally love to see PyGame get more use in education, and I
do think that if children use it, they should be able to contribute.

There are many ways to circumvent that - e.g., I could pass on any
reports and code by young contributors, but it's not the same. Many
people get rewarded for their work on free software with attribution,
and this is even more true for children. There are certainly things that
children should not have published on the internet, but a cool history
of contributions visible under their names and accounts sure is
something that could be beneficial in later life.

Another way to circumvent this would be to accept patches on a second
channel, e.g. mail, and merge Git commits with their original author and
push them to the repository, without requiring the contributor to
register with GitHub, which leads us to the second issue.

As of 2017-02-28, GitHub changed their ToS, adding an even clearer ban
on children, and a requirement to dual-license all work to them. A quite
good analysis of that can be found here
https://www.mirbsd.org/permalinks/wlog-10_e20170301-tg.htm and here
https://joeyh.name/blog/entry/what_I_would_ask_my_lawyers_about_the_new_Github_TOS/
.

I have spoken to two lawyers about that, and they basically say that on
first glance, the ToS are indeed very problematic.

The FSF, in the meantime, has published a post stating that the new ToS
do not conflict with the GPL license family here
https://www.fsf.org/blogs/licensing/do-githubs-updated-terms-of-service-conflict-with-copyleft
(but they still discourage use of GitHub), I (and others) do not think
their view is correct, because the ToS explicitly say that they may use
works without attribution, and the GPL licenses explicitly require
copies to carry attribution. Also, even if the FSF is correct, this only
applies to GPL, and probably not to CC-BY-SA and other licenses
requiring attribution, or even prohibiting sub-licensing under other
licenses.

In any case,

Re: [pygame] github terms of service issues

[Sam Bull]

On Mon, 2017-03-27 at 15:21 +0200, Jorge wrote:
> Am 27.03.2017 um 11:59 schrieb Sam Bull:
> > On Mon, 2017-03-27 at 11:24 +0200, Dominik George wrote:
> > > > I use the tosdr.org plugin, which gives a rating for ToS for a
> > > > website,
> > > > and summarises the points of the license. Might give you a good
> > > > overview, you can view the summary they give here:
> > > > 
> > > > https://tosdr.org/#github
> > > Unfortunately, the analysis provided there discusses the old ToS,
> > > not
> > > those in effect since February.
> > Ah, reported to them that it is out-of-date. Looks like you could
> > contribute some new points directly at https://edit.tosdr.org/ if
> > you
> > feel so inclined.
> Have you considered NotABug or GitLab?

Well, if we're mentioning alternatives, I've still yet to see anything
with a better user experience than Launchpad, which is free for open
source projects, and is open source itself. I still put all my projects
up there.

signature.asc
Description: This is a digitally signed message part

Re: [pygame] github terms of service issues

[Jorge]

Am 27.03.2017 um 11:59 schrieb Sam Bull:
> On Mon, 2017-03-27 at 11:24 +0200, Dominik George wrote:
>>> I use the tosdr.org plugin, which gives a rating for ToS for a
>>> website,
>>> and summarises the points of the license. Might give you a good
>>> overview, you can view the summary they give here:
>>>
>>> https://tosdr.org/#github
>> Unfortunately, the analysis provided there discusses the old ToS, not
>> those in effect since February.
> Ah, reported to them that it is out-of-date. Looks like you could
> contribute some new points directly at https://edit.tosdr.org/ if you
> feel so inclined.

Have you considered NotABug  or GitLab
?

Re: [pygame] Dirty rect overlapping optimizations

[René Dudfield]

The use case is to speed up naieve drawing. With things like pygame zero,
where they update the whole screen no matter what you draw. Where if people
just draw several images to the screen, we should be able to easily track
their changes, and only update what has changed.

Yeah! Batching APIs would be a useful additions indeed. Ones which do
_multi things at once. The tricky bit is to finding a set of those
functions which are useful for many cases. Also extending the API without
adding a million different functions here and there. fill_multi, blit_multi
etc. However, what does blit_multi do? Blit one surface to multiple places?
What about blit blend arguments? What about sub rects? Shouldn't there be a
batch API for blitting a lot of different surfaces to different rects at
once? After all this you can see how the APIs could get complicated and the
number of them large. We have drawline, and drawlines, do we have blit and
blits?

Relatedly, there is also a possibility of compiling the sprite classes in
Cython. This may also give a decent speedup in some cases. As shown by
things like psyco, and pypy speeding them up. They're loops in python after
all. But I wonder if they can be compiled easily, or if they're too dynamic.

Apart from the jit work going on using libjit, it would be useful to do
data aware blits. What I mean by that is by looking at an image, you can
find better ways to draw it. Eg. does the image only contain 6bits worth of
colour? Then an RLE blit is the fastest, and using 32bit alpha transparency
is wrong. Are there large areas of the same colour (which can be more
quickly drawn with fill())? Can we split it into 5 surfaces (four on the
edges, one in the middle) where only the edge surfaces are drawn with the
much slower alpha transparency blitters? For many games, the images don't
change, so this works quite well. However this would perhaps require quite
an API change (not entirely sure of that), or could likely be implemented
inside the sprite classes with some trickery.

Another area is better memory alignment on a platform specific basis can
give considerable gains. On the slower raspberry pi for example, 16 byte,
and 32 byte aligned memory goes much faster. On many platforms this is 4
bytes, or 8 bytes. Gains of around 600MB/s ->1300MB/s have been seen. This
is one area where a libjit based blitter (or one like in ANGLE) can make
significant improvements. This type of change only needs to happen where we
allocate memory for surfaces (or maybe people have done that already).

Finally, hardware support for things like jpeg drawing, and DMA are
possibilities. For example, the raspberrypi has dedicated hardware for jpeg
decoding (as does most hardware these days). This can be used to draw a
jpeg from memory into a buffer, so if you are drawing photos onto the
screen, then this is a very fast way to do it. However, this would require
a more abstract Sprite class which loads files itself.
Sprite('mybigphoto.jpg'). But interestingly (but not unexpectedly) the CPUs
are outperforming the dedicated hardware, if you dedicate the CPUs to the
task. Also for when the images are small. However, the older, and slower
CPUs don't.
https://info-beamer.com/blog/omx-jpeg-decoding-performance-vs-libjpeg-turbo
But either way, keeping the jpg photos in memory allows you to draw a lot
more of them, than if you decode them and use up all of the limited memory
on small platforms like the Orange|Raspberry PI. So we need a
Sprite('photo.jpg') style api for this reason.

I'm interested in if anyone has done any work on dirty rect optimizations
for reducing over draw for now. Because that could be applied to something
like pygame zero with almost no work on their part, and no work on the
users part. For non-worst cases, like where there's < 50 rects, I guess
simply compiling an algorithm like DR0ID has done in C/Cython will work
nicely enough - if the python code isn't fast enough already. Would need
some representative pygamezero examples to check this.




On Mon, Mar 27, 2017 at 3:55 AM, Leif Theden  wrote:

> Just to clarify, this is an optimization to update the display surface?
> TBH, if DR0ID says that it isn't a good optimization, then I'll have to
> follow him.  Thinking deeply about the issue, the would be better payoffs
> by finding way to not flip bits in the display surface in the first place.
> To say it another way, if we can inform developers that they are drawing to
> specific areas in the display surface several times, then it would help
> profile the game better and reduce extraneous draws.  Android has options
> to detect extraneous overdraw, and I'm sure other platforms do as well.
>
> Also, if we are going to promote pygame group rendering, a cheap 15-20%
> performance increase (based on my system) could be had by creating a C
> function that accepts a list of surfaces and their positions, then
> executing the blits in C.  I've brought it up before, but nothing came if
> it.  In fact, I was 

Re: [pygame] github terms of service issues

[Sam Bull]

On Mon, 2017-03-27 at 11:24 +0200, Dominik George wrote:
> > I use the tosdr.org plugin, which gives a rating for ToS for a
> > website,
> > and summarises the points of the license. Might give you a good
> > overview, you can view the summary they give here:
> > 
> > https://tosdr.org/#github
> Unfortunately, the analysis provided there discusses the old ToS, not
> those in effect since February.

Ah, reported to them that it is out-of-date. Looks like you could
contribute some new points directly at https://edit.tosdr.org/ if you
feel so inclined.

signature.asc
Description: This is a digitally signed message part

Re: [pygame] github terms of service issues

[Dominik George]

Hi,

>I use the tosdr.org plugin, which gives a rating for ToS for a website,
>and summarises the points of the license. Might give you a good
>overview, you can view the summary they give here:
>
>https://tosdr.org/#github

Unfortunately, the analysis provided there discusses the old ToS, not those in 
effect since February.

-nik

Re: [pygame] github terms of service issues

[René Dudfield]

Cool website/plugin.

On Mon, Mar 27, 2017 at 10:56 AM, Sam Bull  wrote:

> On Mon, 2017-03-27 at 10:43 +0200, René Dudfield wrote:
> > Some issues about the github Terms of Service have been raised by
> > Dominik George‏.
> >
> > I'd like to pause the github move until we can find out more.
> > Hopefully he will provide some more information for us soon on what
> > those issues are exactly.
>
> I use the tosdr.org plugin, which gives a rating for ToS for a website,
> and summarises the points of the license. Might give you a good
> overview, you can view the summary they give here:
>
> https://tosdr.org/#github
>
> Biggest issues I see in that summary are:
>
> You must provide your legal name upon registration
>
> Your account can be suspended and your data deleted any time for any
> reason

Re: [pygame] github terms of service issues

[Dominik George]

Hi,

>Some issues about the github Terms of Service have been raised by
>Dominik
>George‏.
>
>I'd like to pause the github move until we can find out more. Hopefully
>he
>will provide some more information for us soon on what those issues are
>exactly.

Yep, give me a bit of time to follow up.

While lengthy discussions about the general issues can easily be found, there 
are some aspects important specifically for PyGame, and I need to put those 
into a comprehensive text.

I will start doing that once I get to my desk through city traffic.

-nik

Re: [pygame] github terms of service issues

[René Dudfield]

Thanks heaps Dominik.  Sorry, I didn't mean to imply there was a rush.

On Mon, Mar 27, 2017 at 10:50 AM, Dominik George  wrote:

> Hi,
>
> >Some issues about the github Terms of Service have been raised by
> >Dominik
> >George‏.
> >
> >I'd like to pause the github move until we can find out more. Hopefully
> >he
> >will provide some more information for us soon on what those issues are
> >exactly.
>
> Yep, give me a bit of time to follow up.
>
> While lengthy discussions about the general issues can easily be found,
> there are some aspects important specifically for PyGame, and I need to put
> those into a comprehensive text.
>
> I will start doing that once I get to my desk through city traffic.
>
> -nik
>

Re: [pygame] github terms of service issues

[Sam Bull]

On Mon, 2017-03-27 at 10:43 +0200, René Dudfield wrote:
> Some issues about the github Terms of Service have been raised by
> Dominik George‏.
> 
> I'd like to pause the github move until we can find out more.
> Hopefully he will provide some more information for us soon on what
> those issues are exactly.

I use the tosdr.org plugin, which gives a rating for ToS for a website,
and summarises the points of the license. Might give you a good
overview, you can view the summary they give here:

https://tosdr.org/#github

Biggest issues I see in that summary are:

You must provide your legal name upon registration

Your account can be suspended and your data deleted any time for any
reason

signature.asc
Description: This is a digitally signed message part

[pygame] github terms of service issues

[René Dudfield]

Some issues about the github Terms of Service have been raised by Dominik
George‏.

I'd like to pause the github move until we can find out more. Hopefully he
will provide some more information for us soon on what those issues are
exactly.


cheers,