* 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).