* shr and background colour
@ 2010-11-30 19:31 Adam Sjøgren
2010-12-01 9:39 ` Julien Danjou
0 siblings, 1 reply; 11+ messages in thread
From: Adam Sjøgren @ 2010-11-30 19:31 UTC (permalink / raw)
To: ding
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
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: shr and background colour
2010-11-30 19:31 shr and background colour Adam Sjøgren
@ 2010-12-01 9:39 ` Julien Danjou
2010-12-01 17:12 ` rtrees (was: shr and background colour) Lars Magne Ingebrigtsen
0 siblings, 1 reply; 11+ messages in thread
From: Julien Danjou @ 2010-12-01 9:39 UTC (permalink / raw)
To: ding
[-- 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 --]
^ permalink raw reply [flat|nested] 11+ messages in thread
* rtrees (was: shr and background colour)
2010-12-01 9:39 ` Julien Danjou
@ 2010-12-01 17:12 ` Lars Magne Ingebrigtsen
2010-12-01 17:59 ` rtrees Julien Danjou
2010-12-01 18:29 ` rtrees Jason Riedy
0 siblings, 2 replies; 11+ messages in thread
From: Lars Magne Ingebrigtsen @ 2010-12-01 17:12 UTC (permalink / raw)
To: ding
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
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: rtrees
2010-12-01 17:12 ` rtrees (was: shr and background colour) Lars Magne Ingebrigtsen
@ 2010-12-01 17:59 ` Julien Danjou
2010-12-01 18:29 ` rtrees Jason Riedy
1 sibling, 0 replies; 11+ messages in thread
From: Julien Danjou @ 2010-12-01 17:59 UTC (permalink / raw)
To: ding
[-- 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 --]
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: rtrees
2010-12-01 17:12 ` rtrees (was: shr and background colour) Lars Magne Ingebrigtsen
2010-12-01 17:59 ` rtrees Julien Danjou
@ 2010-12-01 18:29 ` Jason Riedy
2010-12-01 18:34 ` rtrees Lars Magne Ingebrigtsen
1 sibling, 1 reply; 11+ messages in thread
From: Jason Riedy @ 2010-12-01 18:29 UTC (permalink / raw)
To: ding
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
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: rtrees
2010-12-01 18:29 ` rtrees Jason Riedy
@ 2010-12-01 18:34 ` Lars Magne Ingebrigtsen
2010-12-01 18:36 ` rtrees Lars Magne Ingebrigtsen
0 siblings, 1 reply; 11+ messages in thread
From: Lars Magne Ingebrigtsen @ 2010-12-01 18:34 UTC (permalink / raw)
To: ding
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
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: rtrees
2010-12-01 18:34 ` rtrees Lars Magne Ingebrigtsen
@ 2010-12-01 18:36 ` Lars Magne Ingebrigtsen
2010-12-01 20:26 ` rtrees Lars Magne Ingebrigtsen
0 siblings, 1 reply; 11+ messages in thread
From: Lars Magne Ingebrigtsen @ 2010-12-01 18:36 UTC (permalink / raw)
To: ding
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
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: rtrees
2010-12-01 18:36 ` rtrees Lars Magne Ingebrigtsen
@ 2010-12-01 20:26 ` Lars Magne Ingebrigtsen
2010-12-02 9:49 ` rtrees Julien Danjou
2010-12-02 16:16 ` rtrees Lars Magne Ingebrigtsen
0 siblings, 2 replies; 11+ messages in thread
From: Lars Magne Ingebrigtsen @ 2010-12-01 20:26 UTC (permalink / raw)
To: ding
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
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: rtrees
2010-12-01 20:26 ` rtrees Lars Magne Ingebrigtsen
@ 2010-12-02 9:49 ` Julien Danjou
2010-12-02 16:16 ` rtrees Lars Magne Ingebrigtsen
1 sibling, 0 replies; 11+ messages in thread
From: Julien Danjou @ 2010-12-02 9:49 UTC (permalink / raw)
To: ding
[-- 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 --]
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: rtrees
2010-12-01 20:26 ` rtrees Lars Magne Ingebrigtsen
2010-12-02 9:49 ` rtrees Julien Danjou
@ 2010-12-02 16:16 ` Lars Magne Ingebrigtsen
2010-12-02 17:47 ` rtrees Lars Magne Ingebrigtsen
1 sibling, 1 reply; 11+ messages in thread
From: Lars Magne Ingebrigtsen @ 2010-12-02 16:16 UTC (permalink / raw)
To: ding
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
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: rtrees
2010-12-02 16:16 ` rtrees Lars Magne Ingebrigtsen
@ 2010-12-02 17:47 ` Lars Magne Ingebrigtsen
0 siblings, 0 replies; 11+ messages in thread
From: Lars Magne Ingebrigtsen @ 2010-12-02 17:47 UTC (permalink / raw)
To: ding
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
^ permalink raw reply [flat|nested] 11+ messages in thread
end of thread, other threads:[~2010-12-02 17:47 UTC | newest]
Thread overview: 11+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2010-11-30 19:31 shr and background colour Adam Sjøgren
2010-12-01 9:39 ` Julien Danjou
2010-12-01 17:12 ` rtrees (was: shr and background colour) Lars Magne Ingebrigtsen
2010-12-01 17:59 ` rtrees Julien Danjou
2010-12-01 18:29 ` rtrees Jason Riedy
2010-12-01 18:34 ` rtrees Lars Magne Ingebrigtsen
2010-12-01 18:36 ` rtrees Lars Magne Ingebrigtsen
2010-12-01 20:26 ` rtrees Lars Magne Ingebrigtsen
2010-12-02 9:49 ` rtrees Julien Danjou
2010-12-02 16:16 ` rtrees Lars Magne Ingebrigtsen
2010-12-02 17:47 ` rtrees Lars Magne Ingebrigtsen
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).