shr and background colour

shr and background colour

[Adam Sjøgren]

In news.gmane.org gwene.org.debian.planet.rss:1333 is an example of the
background colour seemingly "overflowing"; screenshot:

 * http://koldfront.dk/misc/gnus/shr-background.png

I don't know if the HTML is broken, but the blogpost looks ok in Firefox
here:

 * http://noone.org/blog/English/Computer/Debian/CoolTools/ccal.futile


  Best regards,

    Adam

-- 
 "Subdued flamboyance"                                        Adam Sjøgren
                                                         asjo@koldfront.dk

Re: shr and background colour

[Julien Danjou]

[-- Attachment #1: Type: text/plain, Size: 690 bytes --]

On Tue, Nov 30 2010, Adam Sjøgren wrote:

> In news.gmane.org gwene.org.debian.planet.rss:1333 is an example of the
> background colour seemingly "overflowing"; screenshot:
>
>  * http://koldfront.dk/misc/gnus/shr-background.png
>
> I don't know if the HTML is broken, but the blogpost looks ok in Firefox
> here:
>
>  * http://noone.org/blog/English/Computer/Debian/CoolTools/ccal.futile

Yes, there's a bug in the background rendering. I know about it, but
it's tricky to fix and since I've the feeling that Lars will come with
something new on that part of the code, I'm delaying the fix. :)

-- 
Julien Danjou
// ᐰ <julien@danjou.info>   http://julien.danjou.info

[-- Attachment #2: Type: application/pgp-signature, Size: 197 bytes --]

rtrees (was: shr and background colour)

[Lars Magne Ingebrigtsen]

Julien Danjou <julien@danjou.info> writes:

> Yes, there's a bug in the background rendering. I know about it, but
> it's tricky to fix and since I've the feeling that Lars will come with
> something new on that part of the code, I'm delaying the fix. :)

Harrumph.  :-)

Sure.  Right now, however, I'm thinking about how to implement the
message range trees, and whether to use self-balanced binary trees or
not.  They all seem to require more storage (and more storage is more
consing), so perhaps not...

The most difficult thing is deciding on a name, though.  "rtrees"?  As
in "range trees"?  Since each node will represent an article range?
Hm...

-- 
(domestic pets only, the antidote for overdose, milk.)
  larsi@gnus.org * Lars Magne Ingebrigtsen

Re: rtrees

[Julien Danjou]

[-- Attachment #1: Type: text/plain, Size: 303 bytes --]

On Wed, Dec 01 2010, Lars Magne Ingebrigtsen wrote:

> The most difficult thing is deciding on a name, though.  "rtrees"?  As
> in "range trees"?  Since each node will represent an article range?

or `range-tree' ? :)

-- 
Julien Danjou
// ᐰ <julien@danjou.info>   http://julien.danjou.info

[-- Attachment #2: Type: application/pgp-signature, Size: 197 bytes --]

Re: rtrees

[Jason Riedy]

And Lars Magne Ingebrigtsen writes:
> The most difficult thing is deciding on a name, though.  "rtrees"?  As
> in "range trees"?  Since each node will represent an article range?

Interval tree is a common name.

Jason

Re: rtrees

[Lars Magne Ingebrigtsen]

Jason Riedy <jason@acm.org> writes:

> Interval tree is a common name.

Oh, nice.  itree.el, then.  Now I can begin typing.  :-)

-- 
(domestic pets only, the antidote for overdose, milk.)
  larsi@gnus.org * Lars Magne Ingebrigtsen

Re: rtrees

[Lars Magne Ingebrigtsen]

Lars Magne Ingebrigtsen <larsi@gnus.org> writes:

> Oh, nice.  itree.el, then.

Hm.  It appears that interval trees allow overlapping intervals.
Perhaps I'll just go with rtree.el...

-- 
(domestic pets only, the antidote for overdose, milk.)
  larsi@gnus.org * Lars Magne Ingebrigtsen

Re: rtrees

[Lars Magne Ingebrigtsen]

It's benchmarkin' time.

For the first test, we'll enter a new group that has only unread
articles, and select the last 100000 articles.  Then the current
"unread" list constructed will basically be, say, 

(setq range '((50000 . 150000)))

(length (setq list (gnus-uncompress-range range)))
=> 100001

(benchmark-run-compiled 1 (dotimes (i 100000) (gnus-member-of-range 100000 range)))
(0.058698999999999994 0 0.0)

(benchmark-run-compiled 1 (dotimes (i 100000) (memq 100000 list)))
(11.471638 0 0.0)

Just using the uncompressed range is a huge win here, of course.  And
the new tree solution is slightly faster:

(benchmark-run-compiled 1 (dotimes (i 100000) (rtree-memq at 100000)))
(0.031434 0 0.0)

I've used the list of replied articles in this group.  It's a kind of
degenerate range thing, since it's mostly just single, non-consecutive
numbers, so we'd expect the simple memq to be faster than range-memq.

(length list)
=> 1848

(length range)
=> 1310

(benchmark-run-compiled 1 (dotimes (i 100000) (gnus-member-of-range 74500 range)))
(30.022137 0 0.0)

(benchmark-run-compiled 1 (dotimes (i 100000) (memq 74500 list)))
(0.47300300000000006 0 0.0)

And it is, the built-in memq winds overwhelmingly.

But what about the new tree thing:

(benchmark-run-compiled 1 (dotimes (i 100000) (rtree-memq rt 74500)))
(0.41015 0 0.0)

Yay.  So it's slightly better than the list solution, even in this
situation. 

So there we have it.  The current memq solution degrades badly on large
numbers of articles, and the gnus-member-of-range solution would have
really sucked on "sparse range" lists, which you get in older groups
where you have read/answered/etc articles over a long time, while the
new rtree solution is stably faster in every¹ situation.

Oh, let's not forget timing the actual conversion from ranges to
lists/trees:

(benchmark-run-compiled 1 (dotimes (i 100) (gnus-uncompress-range range)))
(4.2072400000000005 26 3.252687999999921)

(benchmark-run-compiled 1 (dotimes (i 100) (rtree-make range)))
(0.000116 0 0.0)

Ahem.  :-)

But that's with the very small range...  let's test the reply-range
thing.  rtree should be much slower there...

(benchmark-run-compiled 1 (dotimes (i 1000) (gnus-uncompress-range range)))
(0.945312 5 0.618912999999992)

(benchmark-run-compiled 1 (dotimes (i 1000) (rtree-make range)))
(2.554534 12 1.494542999999993)

And it is, but it's not like this is done a 1000 times upon group entry,
either...

---
¹) "Every" is here defines as "both tested scenarios".

-- 
(domestic pets only, the antidote for overdose, milk.)
  larsi@gnus.org * Lars Magne Ingebrigtsen

Re: rtrees

[Julien Danjou]

[-- Attachment #1: Type: text/plain, Size: 103 bytes --]


*clap* *clap* *clap*

-- 
Julien Danjou
// ᐰ <julien@danjou.info>   http://julien.danjou.info

[-- Attachment #2: Type: application/pgp-signature, Size: 197 bytes --]

Re: rtrees

[Lars Magne Ingebrigtsen]

Lars Magne Ingebrigtsen <larsi@gnus.org> writes:

> (benchmark-run-compiled 1 (dotimes (i 100000) (memq 74500 list)))
> (0.47300300000000006 0 0.0)
>
> And it is, the built-in memq winds overwhelmingly.
>
> But what about the new tree thing:
>
> (benchmark-run-compiled 1 (dotimes (i 100000) (rtree-memq rt 74500)))
> (0.41015 0 0.0)
>
> Yay.  So it's slightly better than the list solution, even in this
> situation. 

D'oh.  I made rtree-memq recursive, even though that's totally
unnecessary.  Rewriting it as a loop gives:

(benchmark-run-compiled 1 (dotimes (i 100000) (rtree-memq rtree 74500)))
(0.30733699999999997 0 0.0)

Hah.

-- 
(domestic pets only, the antidote for overdose, milk.)
  larsi@gnus.org * Lars Magne Ingebrigtsen

Re: rtrees

[Lars Magne Ingebrigtsen]

I think I now have the basic stuff implemented (rtree-memq, -delq, -add,
as well as serialising/deserialising), so it's possible to consider
starting rewriting the summary code to use rtree.el now.  However, I
don't think I'll have time this weekend, so you're all safe...  for
now... 

-- 
(domestic pets only, the antidote for overdose, milk.)
  larsi@gnus.org * Lars Magne Ingebrigtsen