XSF Discussion - 2017-02-16

If I'll ever going to write a server-side PARS [xep 379], I'll call it SPARSE: Server-side Pre-Authenticated Roster Subscription Emission.

is the board meeting *still* going on? *glances at topic*

:D

Guus: ha, so awesome!

And so I added 'MUC subject' to https://wiki.xmpp.org/web/Usability/Glossary

should section1 and section2 headings in XEPs be capitalized?

actually any headings.

I have started working on ISR-SASL2. In case you want to have a look at the first alpha quality draft and provide early feedback: http://geekplace.eu/xeps/xep-isr-sasl2/xep-isr-sasl2.html

Flow, Just submit it.

Flow: nitpick > It MUST not contain whitespace characters. that should probably be MUST NOT

Also I still dislike the term "Nonza".

dwd, "wtf-za" is better

nyco, of "stream first-born child", maybe... or not

nyco, "Element" is suitable in almost every case, and a term of art much more widely known.

dwd, nah too simple

dwd: aren't elements the things you can stuff into your messages?

nyco, I just dislike inventing jargon for the sake of it.

it would have to be stream-level elements to be precise, and that’s long

let's abbreviate Stream-Level Element as SLE and call it a SLEnza.

jonasw, Only in cases where the distinction is needed.

jonasw, I mean, we use "session" quite happily in multiple senses, and we use "node" pretty much everywhere. I don't understand why we needed to have a made-up word for "non-routable stream-level element".

Stream Level Anti Stanza Hop (SLASH)

dwd: because ambiguous protocol references are ambiguous.

Ge0rG, Sure. But what's ambiguous about, for example "followed by a <authenticate/> element", as opposed to using a made-up word?

I don't like the specific word very much either, but at least it is a well-defined term for a well-defined thing in XMPP, which makes it much better than much of our other terminology.

I dislike nonza fairly intensely :)

For much the same reason, it's inventing a word that doesn't need inventing.

If you read the intro to https://tools.ietf.org/html/rfc6120#section-8 then you'll realize that nonzas are stanzas, too.

huh, I thought that stanzas are limited to the jabber:{client,server} namespaces?

and also {iq,message,presence} possibly

jonasw, And XEP-0114. Two namespaces defined there.

jonasw: "either party can send XML stanzas. Three kinds of XML stanza are defined for the 'jabber:client' and 'jabber:server' namespaces: <message/>, <presence/>, and <iq/>." - the spec doesn't claim this to be an exhaustive list of stanzas.

well, okay, but that doesn’t mean that any stream-level element is a stanza, does it, Ge0rG?

Ge0rG, Right. And XEP-0360 simply says everything not a stanza is a nonza.

oh, §4.1 is the important one: Definition of XML Stanza: An XML stanza is the basic unit of meaning in XMPP. A stanza is a first-level element (at depth=1 of the stream) whose element name is "message", "presence", or "iq" and whose qualifying namespace is 'jabber:client' or 'jabber:server'.

Ge0rG, Except that's not true.

What about jabber:component:something

By contrast, a first-level element qualified by any other namespace is not an XML stanza (stream errors, stream features, TLS-related elements, SASL-related elements, etc.), nor is a <message/>, <presence/>, or <iq/> element that is qualified by the 'jabber:client' or 'jabber:server' namespace but that occurs at a depth other than one (e.g., a <message/> element contained within an extension element (Section 8.4) for reporting purposes), nor is a <message/>, <presence/>, or <iq/> element that is qualified by a namespace other than 'jabber:client' or 'jabber:server'. An XML stanza typically contains one or more child elements (with accompanying attributes, elements, and XML character data) as necessary in order to convey the desired information, which MAY be qualified by any XML namespace (see [XML-NAMES] as well as Section 8.4 in this specification).

For XMPP 2.0, can we just use a single namespace?

it goes on!

dwd: what's not true?

Ge0rG, As Zash says, XEP-0114 carries stanzas in other namespaces.

dwd: no ends of fun because of it.

dwd: 0114 is historical. It doesn't even count. And even if it did, it were wrong, because 6120§4.1

I don't think jabber:(client|server|component) adds anything useful to the protocol that I can see, over a single one.

Ge0rG, A better definition would be that stanzas are stream-level XML elements, with local names "iq", "message", or "presence", within the content namespace of the stream, which may be routed without additional negotiation over other connections (and namespaces).

Ge0rG, But much of that is reversing the defition of a Nonza in XEP-0360.

Kev, No, I agree. It's a distcintion that proves more annoying than useful.

from 114: "Once authenticated, the component can send stanzas through the server and receive stanzas from the server. All stanzas sent to the server MUST possess a 'from' attribute and a 'to' attribute, as in the 'jabber:server' namespace." - I don't even see how this is violating the Stanza definition

The Default Namespace

Kev: +1

dwd: having different terms for routable, standardized stream elements vs. unroutable negotiated ones is very useful. Please rephrasse your critique in a way that still allows for this distinction, without writing out "non-routable top-level stream-elements" every time.

Ge0rG, I'll do so when you can answer the question about when such a precise distinction is warranted above.

Ge0rG, Even when we need to talk about stream-level elements other than stanzas, we can do so clearly (as I just have).

Ge0rG, That, incidentally, requires no reference or document to support it. Whereas even someone well-versed in the RFCs, who has read and implemented a number of XEPs, will not know what "Nonza" means without further reading.

From 0198: "To enable use of stream management, the client sends an <enable/> command to the server." - it's using "command", which is ambiguous and makes me think of ad-hoc commands. There is merely a single mention that 0198 is using not-stanzas at the root level.

Sure, it should say 'element' instead of 'command'.

It doesn't need to say nonza.

dwd: The benefit of "nonza" is actually that the word itself, being a portmanteau of not-stanza, is easy to remember and even to guess from context.

0198 obviously pre-dates the term. My point is that our specs are ambiguous, and that the term helps reducing the ambiguity

It's kinda like abstracting some code into a function

Silly term tho

Kev: it should say 'top-level element', or 'root-level element', so it won't be confused with a <message> or <iq> element.

If anyone reads "an <enable/> element" and thinks "I think it means a <message/> stanza", then I doubt their ability to understand any other part of the stack they need to implement.

Ge0rG, You';re right. I'm convinced by all those people who implemented '198 as an ad-hoc command.

well then, looks like we are done here.

Now, what term do I need to search for if I want to get a list of all XEPs that define new non-routable root-level stream elements?

Okay, enough time spent on bikeshedding today. Another XEPs PR is waiting to be completed.

SamWhited: would you still like to have a revision block added to #413?

Howabout #413

Zash: XEP-280: Improve readability #413 https://github.com/xsf/xeps/pull/413

Bunneh doesn't like me.

Wasn't enabled for this room

Zash: That's what you say. I tell you: robot discrimination can go both ways.

What Ge0rg said.

Also you all had enough time to suggest a term for xep360. :-P It's not like I care about the exact name. But I agree with everything Ge0rg said. A definition for non-stanza top level stream elements was truly missing.

Flow: sorry, you missed the discussion. But the XEP-0368 LC on standards@ could use some more bikeshedding.

Ge0rG: I disagree with everything said in that thread, including what I said myself there

Flow: that'd make a great follow-up post.

Also, 0368 needs a pre-Direct-TLS nonza to inform the other party of an imminent connection security upgrade.

jonasw: Thanks for the hint :)

Ge0rG: I do believe SASL2 probably could do that :)

No what we really should do is make SASL a TLS extension!!

Zash: yay! We could use SNI to send our bare-JID and encode the password in ALPN!

YES!

+also

And use session tickets instead of 198

this doesn’t sound like a bad idea at all!

What is the correct way to attribute XEP changes to external authors? the <initials> element of the <revision> element looks like it's not sufficient.

Flow: wow, that was blazing fast. re #423

Flow: XEP-0379: Added "Usability Considerations", removed actual XMPP client, some text editing. #423 https://github.com/xsf/xeps/pull/423

30 minutes between PR and merge. New record :)

Ge0rG: are you working on 0280 currently?

jonasw: yes

s/elible/eligible/ in the revision history, if that’s legit

jonasw: thanks, added

that 0.10 block is a good example for what I asked above, btw.

Flow, SamWhited: we need to update the "XMPP Extensions Editor" email template to link to https://xmpp.org/ instead of http://

I first want to know what is missing in xep-README that is preventing your updated version to appear at xmpp.org

Flow: if you want to try another attempt: https://github.com/xsf/xeps/pull/413 is ready to merge now.

Ge0rG: the inversion of SHOULD to MUST NOT should *probably* be mentioned in the changelog

ah it is

nevermind

Aww man, all the good rants get taken before I'm a awake: Nonza always just seems like needless tribal knowledge to me too.

I like nonzas.

This is a clear case of majority-vote-needed. Just let us trump it down properly.

speaking of which, is "yes we can make xmpp great again" a better slogan than simply "make xmpp great again"?

jonasw, Twice as presidential.

so much bikeshedding. So little actual input.

"Make Britain Great Again" was the slogan under which Thatcher first stood as an MP.

(It was Churchill's reelection campaign, actually - he won).

I quite like "Make America Great Britain Again"

Now that #413 is as-good-as-approved, I'm going to push forward with my threats from https://mail.jabber.org/pipermail/standards/2017-January/032048.html re MUC-PMs in 45 and 280.

Ge0rG: XEP-280: Improve readability #413 https://github.com/xsf/xeps/pull/413

I'd really like to hear Kev and dwd on that.

It's a huge rewrite.

Which is probably a good thing, but it does mean going over it carefully.

dwd: what is a huge rewrite?

#413 - seems to make a lot of changes to normative language.

dwd: XEP-280: Improve readability #413 https://github.com/xsf/xeps/pull/413

Bunneh, Thanks.

Ge0rG: FWIW, what you wrote regarding MUC-PMs seems reasonable to me, but I haven’t looked in detail yet. also it seems really a server-implementor specific thing, so I cannot really give feedback :/

dwd: I'd like to hear you on https://mail.jabber.org/pipermail/standards/2017-January/032048.html and not on the almost-approved PR, thanks

is there any … information material which shows why matrix is uncool?

well re-inventing the wheel is uncool

jonasw, They spent a huge amount of time and money telling the world that XMPP was terrible.

moparisthebest, that's why XMPP should have just been IRC :)

jonasw, They've stopped that now, mostly. But they still have lots of time and money to spend on publicity. We really need to catch up.

the protocol itself and work done is interesting, my main grief against them is there attitude against XMPP community (it is still visible in the F.A.Q.), and also I'm naturally suspicious with corporate stuff.

goffi, Right, it's still a single company, with a lot of money, pushing their proprietary solution. It's more open than, say, WhatsApp, but not much.

and if we have to compare, I think it's extensibility is a good think in opposition to what they say (that monolitic is better)

MattJ, well IRC didn't federate and had other problems

dwd: I don't say it's not open, I'm just suspicious and I'm more confident with XMPP workflow (which is not perfect either), were I know I can have my word to say

matrix is just xmpp re-written in a less extensible manner with json and webservices meh

it's impressive to see the number of clients/libraries available they already have after 2 years and something

-available

moparisthebest, No, there are some fundamental differences. Mostly that domains are not autonomous.

moparisthebest, and a different data model, not? doesn't it use a tree structure to distribute messages instead of just routing XML pieces like XMPP?

goffi, Yes. Mindshare is important, as is being able to devote some cash to good examples.

dwd, domains not being autonomous? what do you mean by that?

oh great. people complaining about XMPP because it loses messages on mobile. you ask what client they use, they say xabber.

jonasw, Yeah. Matrix don't have this problem because the pool is very small, so far.

Tobias, Chatrooms don't live on one domain exclusively, so aren't under single control.

ahh...so they have federated MUC built in

dwd: that can be a good or bad thing

Tobias, Sort of. FMUC and friends operate on the principle that there is a source of truth, or else that a sort of semi-independence can be achieved.

single control may be needed in some case (enforcing policy for instance), avoiding single point of failure is nice for popular public room

Tobias, Matrix operates on the notion that there is no single source of truth,

how do message deletion/modification works on Matrix?

goffi, Well, XMPP has supported clustered services for years, so there's no *single* point of failure, but the entirety of control resides within a single autonomous domain.

goffi, I have no clue.

git commit --allow-empty -m 'Hello world!'

git push

goffi, I also have never quite worked out how your server knows to stop mirroring the entire chatroom if ever you leave it.

dwd: despite asking them, right?

intosi, I can't decide if that's an ironic statement or a wrong window.

dwd: I'd really like to get your 2¢ on the MUC-PM thing.

goffi: that's probably something they will add an extension - aehm I mean module - to their monolithic spec for later on

daniel, Right, they don't do extensions. They do fork-lift upgrades.

couldn't Matrix be used as a distributed database for XMPP ? Data replication is interesting for directory.

intosi, And yes, I did ask them, once. I can't even recall the answer, though.

or put in other words, would it be possible (and yes it would) to implement a similar thing in XMPP?

goffi, Oh, sure.

Ge0rG: ++ ; thanks for the first "Usability Considerations" section; looking forward to reading that (and Flow ++ for getting it merged so quickly!)

SamWhited: half of it was in the XEP already, part under "Business", part under "Security"

SamWhited: Flow performed the magic, but https://xmpp.org/extensions/xep-0379.html wasn't immediately updated. He wondered why.

SamWhited: also you can merge #413 now, we've provided the <revision> block (plus some revision typos)

SamWhited: XEP-280: Improve readability #413 https://github.com/xsf/xeps/pull/413

SamWhited: and I'd like to move on with my 0280 rewrite ;)

Ge0rG: Thanks, let me go merge that now before I get too deep into the weeds with my day job.

SamWhited: yay!

When you say, "wasn't immediately updated", what actually happened?

SamWhited: I have no idea beyond "12:49:16 Flow> I first want to know what is missing in xep-README that is preventing your updated version to appear at xmpp.org"

i think it requires action from the XEP editor to rerender

SamWhited: btw, I've also encouraged @penguineer to make another PR to xeps/README, describing the contribution process

yah, I'm not sure what that means; is the README not up to date? Maybe I just forgot to update it last time I tweaked things.

I wouldn't add anything people need to be able to discover easily to xep-README; it's just a bunch of technical details for the editors so that we don't forget how to do things

I found out why I failed, everything is fine now

SamWhited: not sure about your version of the README, but the one I see on github is a bunch of links and two hints about the makefile, nothing about the editorial process

Oh, that readme, sorry, different thing.

I have no idea how the editorial process looks like or whether it should be public.

Ge0rG: It's public, it's just probably not something we want to point people too; it's not really written to be consumable or easy to follow.

Yah, I'm sure the GitHub README could be improved; PRs welcome :)

SamWhited: TBH, I don't care too much about how it looks, as long as onboarding new editors works sufficiently well for them.

Maybe we should just merge the two and just have the markdown readme *be* the editor readme.

Although I don't think it will generate a nice table of contents for you, so maybe that would be harder.

SamWhited: I think the README.md should be aimed at contributors first, not at editors.

Ge0rG: Yah, you're right

SamWhited: it's okay to cover editorial tasks further down, but it's not a prio for me

Editors have xep-README.*, right?

SamWhited: and the email template needs to be https'ed.

intosi: Yup: https://xmpp.org/extensions/xep-README.html

wow, that file is impossible to discover :D

I mean, it's not supposed to be hidden, it's just not listed or linked anywhere really

which is not a problem probably.

and is full of confusing details and incorrect information that I haven't updated yet :)

Yah, not a problem as long as contribution details don't go in there (but that was just me getting my README's confused)

All of this meta talk reminds me that I still need an XML schema for 0379. And I'd love to get that contributed by somebody more familiar with schemas

Editor's job to write schemas for people? No, I don't think so.

Something the authors need to do before Draft.

Oh? In that case, nevermind, I'm happy :) thought I read somewhere that if you needed help with the schema the editor was supposed to provide it.

XEP-0143:

> The XMPP Extensions Editor team can assist you in defining an XML Schema for the protocol you are proposing

Maybe I misremember, it happens sometimes.

Oh, help, yes. But not to write the thing.

Or point you to the nearest person who hasn't lost sanity yet?

Kev: I did say "editors job to help with that", not "to write that" :)

You did.

I've lost my sanity a long time ago. Help me please.

I got the wrong end of the piece of rope's back.

The frayed end?

https://xmpp.org/extensions/xep-README.html#updating references an announce.py. Is that part of https://github.com/xsf/xmpp.org ?

Kev: I'd also like to hear your opinion on https://mail.jabber.org/pipermail/standards/2017-January/032048.html before I start writing PRs.

Ge0rG: https://github.com/xsf/xeps/blob/master/announce.py

SamWhited: thanks

SamWhited: #424 :D

SamWhited: gen-scripts: Encrypt all URLs ;-) #424 https://github.com/xsf/xeps/pull/424

Ge0rG: LGTM, thanks.

although it's not encrypting URLs

Tobias: it's not?

No, the URLs are still in plain text :)

damn, that's a security vulnerability. Let me pull a CVE ID fast.

SamWhited: what did you do to change the sha1 of my gen-script commit?

Ge0rG: Used GitHub to merge it instead of doing it myself (which is always a mistake)

I go for one short walk in the sun and I get back to a bazillion messages?

SamWhited: it wasn't even a merge, it rather looks like a rebase. Generally I like rebase more, but it could have been a fast-forward

With GitHub you get your choice of: Add a worthless merge commit with some useless default message, change the hash and get a useless merge commit with a default message, or just change the hash.

We need more options.

Ge0rG: Yah, I agree, this is why I normally don't use GitHub's web interface

SamWhited: I don't mind it at all, I just wondered. Thanks.

Re Matrix: If they do what I think they should, based on what I've heard (because their docs are terrible), it's all basically MAM queries all the time.

Ge0rG: Good eye though; I'm impressed you noticed :)

SamWhited: Switched to branch 'master' Your branch and 'xsf/master' have diverged, and have 1 and 2 different commits each, respectively.

SamWhited: (actually, I saw it in gitk, but this is just a minor thing)

My other project's git history looks like a map of the London Underground. I appreciate linear histories.

(which now reminds me of that one Linux commit that is octomerging 60 different branches)

Should have stuck with Mercurial

It doesn't even allow more than 2 parents :)

Zash: because a series of 60 merge commits is much cleaner than one octomerge? (usually, project that do either are seriously broken)

Or if it does, I have no idea how that would work with the internal data structures I've looked at.

Yah, I feel like if you think you need to merge 60 things, you have other problems and choosing a different VCS isn't going to help.

choosing a different VCS was one of the main culprits of the NTPsec fork.

SamWhited: Having a system that allows it does sorta encourage it tho

Zash: I think that hg only was inveted to troll git users.

Ge0rG: You got it wrong, it was to troll Python 3 users

Zash: yah, I agree, octomerge is dumb

Zash: I'm not part of that audience, but maybe it was meant to troll both.

Probably to troll everyone but SVN users

Zash: I have heavily used svn before git, and hg still makes me stumble every time.

I heavily used SVN, and then HG, and was absolutely an HG fanboy for a while just because it was my first DVCS. Then I realized that we should have learned from our mistakes, and that literally everything was easier and just worked better in Git and that a few minor foibles about the interface not being very consistent should not be enough to stop me from using it, so I learned it and haven't looked back since.

Maybe it's just the order you learn things in

I used svn first, then git, then hg

I like hg the most

Zash: it's the same order for me, and I really can't stand hg. It's trolling me right into my face: hg: unknown command 'fetch' 'fetch' is provided by the following extension: use "hg help extensions" for information on enabling extensions

MattJ: I assume you saw https://github.com/xsf/xeps/pull/420 ?

Ge0rG: That's your brain on git

Zash: no, that's a program telling me: "I know what you want, but I won't let you do it. Instead, you have to read a dozen pages of my useless manual first"

I understand the difference and don't really care between feetch/merge and update/pull, but that specific example aside I do agree that the extension thing always pisses me off.

Ge0rG: I could say the same thing about all the times I've done git pull and wondered why the heck it did a merge

What about a friendly "hg fetch is provided by the 'fetch' extension. Activate? (Y/n)"

Oh, I just don't like the idea that it has extensions at all (I mean, in a sense Git does too, but it's not actually a thing you're supposed to make generic extensions against, it's just how commands work internally)

Not to say that people can't write their own tools to manipulate stuff, I just don't like that it's built right in and it will actually try to get you to use them.

Ge0rG: Here, it yells that fetch is deprecated

Is there any other Elder whom I can summon to be enlightened about the interaction of MUCs, PMs and Carbons?

Elders predate Carbons

Zash: I seriously hope that the Elders predate any of the XMPP protocols.

Zash: you replied to Ge0rGs thread that at least two implementations are already tagging outgoing MUC PMs with <x/>. can you tell me which?

you’re not good at tabcompletion today

jonasw: Prosody and ejabberd ✏

I'm not

I blame Kev. Everything is Kevs fault!

Ge0rG was talking about clients, not servers, I think.

Zash wrote: > a) Require carbon-enabled clients to tag outgoing MUC-PMs with <x/>, > carbon-copy the 'sent' MUC-PM to all clients, require carbon-enabled > clients to check for <x/> tag and to drop if they are not joined. This > is a 90% solution (it will still display outgoing PMs if you are > joined to the same MUC under different nicknames, as the other client > doesn't know which nickname the 'sent' message came from). I believe at least two implementations do this already.

jonasw: I believe I was talking about servers

Zash: you believe? :P

ah, oddly quoted then

Ge0rG: bee-hive

Zash, you mean bhyve? http://bhyve.org/ :P

I wrote a kontalk JID hash to phone number lookup service if anyone is interested https://www.moparisthebest.com/phonehash/

more of a fun learning excercise than anything, but you can look up any 1 of 100 billion phone numbers with it in ~2 seconds

"kaputt" as we say in germany :)

Phone numbers in what format?

Zash, currently supports currently supports 0-000-000-0000 to 9-999-999-9999, which kontalk hashes like '+00000000000'

So basically +%011d then

so I guess it doesn't support 2 digit country codes or strange formats? it'd be easy to generate files with those then

yes all 11 digit phone numbers

Hm, 2TB of storage required for a rainbow table, or is my math wrong?

Zash, I couldn't find really good resources for rainbow tables, so I don't know :)

this only takes 500gb of storage though because I'm not storing any hashes, just the numbers

What

10¹¹ * 24B

(also you could probbaly get away with storing only a unique prefix or part of the hash, reducing the storage needed drastically. after all, a phone number has only 36 bits of entropy)

I explain it all here: https://github.com/moparisthebest/phonehash

20 byte sha1 output + 4 byte number

99,999,999,999 won't quite fit in 4 bytes, you need 5, right?

moparisthebest: nice hack!

congrats on that idea :)

How many bytes is 64 bits again?

8, Zash

yea

Well then

actually iirc that number fits in like 38 bits instead of the 40 bits I'm using

Probably possible to use truncated sha1 hashes, don't think the full output is required to avoid collisions

but unaligned bytes sounded TERRIBLE

Storage is cheap

Maybe I should have done some calculations before attempting to generate this rainbow table in memory

yea but I'm hosting this on my server that only had 800gb of free space hehe

if someone really cared they could get a huge SSD and it'd be faster

Build a big B tree or something

but 90 hours for generation on 2 slow spinners in linux software raid1, and then ~2 seconds per lookup is fine for me

yea I sorted the numbers in the file by hash, but only store the numbers, so I could do a binary search

which for 100 billion numbers is max 26 lookups/sha1 hashes

which my machine can apparantly do in <2 seconds, probably mostly constrained by disk seek speeds

yeah, 26 times sha1 should be *very* cheap

microseconds cheap

it’s the disk :)

during generation I wrote to 65535 files and it KILLED my disk

I had to put in synchronization code so only one file was written to at any given time

so an SSD with no seek time, I bet generation would go from 90 hours to 20 or less

anyone want to send me a >500gb SSD to find out? :P

no.

or run it yourself :P

ENOSPC

Rent some CLOUD

I don't have an SSD with that much free space

or money to burn on a toy idea like this lol

Zash, so how were you calculating how big a rainbow table needed to be?

I couldn't really find good info

the strings being hashed are like +00000000000

so a +, then 11 digits

moparisthebest: But if they are numbers, you can just encode them as digits

err

as computers do

yea but can rainbow tables?

integers

I mean presumably a custom implementation can do whatever it wants

Gaint hash table?

but yea all the tools I found only let you specific 'character set' and 'length', which meant it was doing length of 12

and also trying numbers like '00000+000000'

and I had it do that and using 100% cpu for 4 days only had generated a 4gb file so far

so I stopped it hehe

Hu, I ran into the 1GB memory limit of LuaJIT in a few seconds :/

this was the first time java using a 32-bit signed integer as array indices actually effected me

t [ sha1( sprintf("+%011d", i) ) ] = i for i in 0 → 10^11

yea that's a *lot* of memory

ha, I know why I have swap turned off by default :-)

because just storing the integers as 5 bytes each is 500gb

storing them with 20 byte sha1 hashes is 2.5tb

if you stored them as the 12 character strings they are actually hashed with, that's a TON of space

depending on character encoding and such of course hehe

I’m still amazed by your binary search hack

... binary search what

If you sort them into 256 buckets based on the first byte of sha1, then sort each of those buckets into buckets based on the second byte of sha1 output, and so on, you get a tree thing...

Zash: 256 buckets is a bit big, I sorted them into 65535 buckets based on the first 2 bytes of the sha1 hash, then sorted those, concatenated all of them into one big now sorted file

Isn't that just the definition of a prefix tree?

And then just do a binary search on it

SamWhited: Being self-taught, I rarely know the names of things.

Idk I forgot most of these terms from school :-)

ah, no, this is the phone numbers… sort of a weird mix of prefix tree and binary search.

or a trie or whatever

It's like a bucket sort, what I did

That's where I got the idea anyway

I've seen a physical bucket sort. It was cool.

Mail sorter machine ✏

there I added a tl;dr to the readme

tl;dr I put all 11 digit phone numbers represented as 5 byte integers in a 500gb file sorted by their sha1 hashes, now I can binary search it fast.

https://github.com/moparisthebest/phonehash if I didn't link it already

There are some fun ways to store sets of integers

Like, delta compression

Or a giant bitfield

not sure if any of these work if you have essentially shuffled integers

yea compressing a random set of integers is impossible of course, but these are sequential, but the order is probably essentially random?

it'd be interesting to look into though

If the numbers are divided into blocks of bit fields, then you do a linear search through the bit field but binary search on the blocks...

I have no idea what you just said, why don't you try to implement it then let me look at your code... :)

I have no idea how large a bit field would need to be

Going to implement food instead

Zash: enjoy the debugging!

Instead of the binary search, wouldn't it be faster to jump to index (hash / 2^160) * size and search up or down from there depending on the difference between the hashes? The hashes should be quite uniform.

not entirely positive what you mean xnyhps , sounds interesting to try though, care to explain more?

moparisthebest: you have the data sorted by hashes, so looking at the first 32bit or something to guess the index in your array is a pretty reasonable thing to do

ah yea, interesting

If you were looking for the hash 10000000000000..., you can assume it's close to 1/16th in the list of phone numbers because it's 1/16th of the possible values for the hash.

You'd start at 8000000..., then 4000000..., etc.

it's not clear to me whether that would always be 26 comparisons or less though?

I guess it'd depend on exactly how evenly distributed the hashes were?

Yeah.

sha1 should be pretty uniform

So you basically treat it as a hash table?

it is for some definition of "pretty" :)

You could also do a binary search, but with a weighted "middle" value.

so like when I sorted it into 65535 different files based on the first 2 bytes, if it was *perfectly* distributed the files should have all been like 7.3mb, but they ranged between ~7 and 7.8 or so

moparisthebest: 10^11 is a pretty small sample size tho :)

I should have taken exact byte counts at the time

You could have just kept the files as is

yea could have, more math than just jumping to a place in one file though

Wouldn't it be exactly the same math, just a smaller file?

like I already had the code written to do a binary search in one file and didn't want to bother doing anything else hehe

and you get told the right file to open from the input

and it was the same amount of disk writing, read file into memory, sort file, write file to same file or append to one file is the same

ah yea that's true, yea that would have been faster

well I'm not redoing it haha

And then jumping to some point based on the 3rd byte of the input and done a linear search from there

it would be faster but it's not faster by a huge margin log(100000000000/65535) is 15 sha1+comparison worst case vs 26 for the whole 100 billion

still that would have been better :)

moparisthebest: it will be quite a bit faster

Don't underestimate the performance of linear searches. CPUs, kernels and the disk can be much smarter

sequential access is good for spinnign disks

probably you will have only a single access because all of the numbers fit in the same block

maybe two disk accesses

binary search mucks up all the caches and whatnot

I guess the disk latency is the most expensive thing here, and that will vanish to O(1) instead of O(log n)

yea it'd be interesting to see how much it improves

it's already <2 seconds though, if I reworked it like that what would it drop to, 1?

hmm

100ms or something maybe, from a naive calculation

well also I can see how a forward sequential read would be faster

but jumping to a place might put me ahead of it too which would cause a reverse sequential read

which would equally negate caching

hm, maybe

this then really depends on the block alignment

the disk cache is what benefits your application the most, I think, and that is controlled by the block alignment. unless you hit a block boundary you should be fine. and that can happen both ways.

on a more on-topic manner, has there been discussion about introducing {urn:xmpp:mix:0}feature elements in disco query responses? I do not like that idea.

Wha?

Zash: e.g. example 40 in xep 369

-xep 369 ex 40

Zash: http://xmpp.org/extensions/xep-0369.html#example-40

woah, dem features

(pun not intended)

Hnnng

I cannot interpret that

<grunt-of-disapproval/>

No caps?

not sure if mix channels are supposed to support caps :)

but the interaction with caps would for sure be interesting

so based on a clients support or mix or not, could a server allow them into a mix channel if supported or throw them into some type of muc compatibility layer for the mix jid if not?

sounds super hacky and terrible from a server POV but nice and cozy from a client/user POV :)

ie client A supports mix, client B supports muc, both try to join room@example.org, end up joining same room but B is using his servers muc->mix layer?

since mix requires server support anyway, at least it wouldn't *require* client support this way

plus I'm sure that sounds like loads of fun to implement for Zash

hey it'd work the other way around too, servers could treat remote MUCs as MIXs for their clients that supported MIX ? :)

good night everyone ☺

alright SamWhited it's up https://github.com/xsf/xeps/pull/426