What follows might just be nonsense, but I'm still speaking out. For the trees, you understand.
On Mon, Apr 6, 2009 at 5:19 PM, Dave Cridland <d...@cridland.net> wrote: [snip] > You want to replace 2-4 with: > > 2') Home server collates roster by remote domain and emits one presence > stanza per remote domain which has a subscribed contacts known to be > available. This is, I'll accept, likely to be close to the energy cost of 2, > although due to the fluctuating nature of the final clause that collation > has to be done each time, so it'll be a little above. Cost E2' is, therefore > > E2. > O(n) + O(d) - I have a feeling this can be reduced to O(n). > Keep a list of domains (affectively a cache) to send to along with the roster object (possibly even storing it on disk along with the roster), and E2' becomes less than E2. > 3') encode/transmit/decode 1 stanza per remote domain. This is certainly an > energy/cpu/cost saving compared to the 3 above, no argument from me here. > Cost E3' is < E3. O(d) (One stanza per domain. Still linear, of course). > > 4') Lookup sender against all rosters in the system, and detirmine which of > the resulting potential recipients is online and available to the sender. It > seems reasonable that it would be possible to limit the lookup to only > contacts who are online and available - assuming we ignore privacy lists - > but you're still adding a lookup and the associating lookup mechanics (like > a hash table or something) which must be maintained in-memory. I strongly > suspect that this much, much more costly to use, build, and maintain than 4 > above, hence E4' >> E4. I believe this to be possible to implement as > O(log(y)), but I also suspect it's overwhemlingly more likely that it's O(y) > (as derived from a reverse roster lookup O(log(y)) combined with a > resource-broadcast lookup O(y)). > I don't think E4' >> E4. I think E4' < E4. "you're still adding a lookup" you say. No, this replaces y hashtable lookups with one lookup. Think about it. While yes, a hashtable would indeed need to be maintained, the resource usage wouldn't be significant. The additional memory cost would be an order of magnitude less than what in-memory rosters already use. The hashtable update/remove cost would only apply when local resources become unavailable/available, which tends to happen only once for most c2s sessions. Presence broadcast on the other hand tends to happen more than once (at least that's what it looks like for my contacts). Simply stated, writes would be (much?) rarer than reads, and read cost would be reduced by a reverse hashtable (think of database indexes). > This give E' as O(n) + O(d) + O(y), a linear compexity algorithm. Poof goes > your argument above about linear complexity versus constant amortized time. > The Big-O notation is about complexity, not cost. While two different algorithms may both have the same complexity, that does not imply that the resource cost is the same, or even close. Several optimizations reduce cost, but not complexity (making certain boolean checks unnecessary, for example). And since the topic is trees, the resources being consumed by the intermediate nodes (routers, etc), should be added to the equation. > I can't see (E3' - E3) < ((E4' - E4) + (E2' - E2)) as being at all likely, > so I continue to maintain that this is a false optimization. (I also > continue to maintain that this is an arse-clenchingly more complex solution > to the problem of getting presence from one contact to another, but I hope > nobody's arguing against me, there). > > Now, as always, I encourage you to change my mind with suitably backed > factual evidence. > I suspect the CPU cost would be lower with this proposal. Saved bandwidth was more appealing to me than saved CPU time, but the missing unsubscribed issue makes this optimization invalid, so no point in attempting tests. > Oh, and I would add that this does, of course, change dramatically if we > introduce a non-meshed routing architecture between servers - since that > reassociates responsibility anyway, it's not a problem there. (FWIW, I would > note that this already occurs between client and home server). > > Dave. > -- > Dave Cridland - mailto:d...@cridland.net - xmpp:d...@dave.cridland.net > - acap://acap.dave.cridland.net/byowner/user/dwd/bookmarks/ > - http://dave.cridland.net/ > Infotrope Polymer - ACAP, IMAP, ESMTP, and Lemonade > -- Waqas Hussain
