Show Idle (>14 d.) Chans
← 2022-12-24 | 2022-12-26 → ↓
jonsykkel[asciilifeform]: asciilifeform wat exactly is this unordred_set with o(1) insert/delete?
jonsykkel[asciilifeform]: either way i think there is simpler way to do wihtout 1800 magic vector structures
jonsykkel[asciilifeform]: where u just decide on max packet rate and determine static bufer sizes based on that
jonsykkel[asciilifeform]: it requires u to use system clok insted of packet.stamp to retain o(1) insert
jonsykkel[asciilifeform]: but that dosnt mater cuz theres a upper bound on the difference between those. simply means bufer will have to be sized for worst case
phf[asciilifeform]: "asciilifeform discovers cpp std"
phf[asciilifeform]: also merry christmas
phf[asciilifeform]: cookies and spiked eggnog hangovers are the worst, i don't know how santa does it
asciilifeform: phf: asciilifeform did hard time in cpp mines, long ago. but mostly fughot the horrors.
shinohai[busybot]: Merry Christmas all
bitbot[asciilifeform]: Logged on 2022-12-25 05:53:54 jonsykkel: asciilifeform wat exactly is this unordred_set with o(1) insert/delete?
asciilifeform: http://logs.bitdash.io/pest/2022-12-25#1019255 << wrote the actual proggy with cheapo linked lists rather than expandable arrays
bitbot[asciilifeform]: Logged on 2022-12-25 05:54:23 jonsykkel: either way i think there is simpler way to do wihtout 1800 magic vector structures
asciilifeform: http://logs.bitdash.io/pest/2022-12-25#1019256 << this was the 1st algo asciilifeform considered, and rejected -- it often lets entries sit far longer than they gotta, and isn't much less expensive than asciilifeform's proposed algo afaik
bitbot[asciilifeform]: Logged on 2022-12-25 05:54:26 jonsykkel: where u just decide on max packet rate and determine static bufer sizes based on that
asciilifeform: ( likely -- substantially ~moar~ expensive, on acct of overripe entries )
asciilifeform: prolly oughta test empirically tho
asciilifeform: ( still not sure how jonsykkel's could possibly win anyffin, other than saving coupla kB of mem, in total, from having 1 linked list rather than 1800 )
asciilifeform: per spec, ftr, 'A station’s Filter is a data structure which retains a hash of every valid incoming and originated Message, until such a time that if a duplicate of that Message were received, it would be deemed stale.'
asciilifeform: wainot actually implement the spec.
asciilifeform: observe that filter stores hashes of all msgs, not only chained; and emitted as well as received. letting'em all sit for potentially 15 extra min. is mega-bloat, esp. after we have signpost's luby
asciilifeform: the 1 boojum asciilifeform can presently think of is that it aint threadsafe (needs lock, given as tick() runs async.)
asciilifeform: ( obviously missing is the timer per se, and check for ticks <= maxTicks; but imho these belong in the packet receiver )
asciilifeform: ditto re the check whether already contains $item.
asciilifeform starts to think that in the process of posting this, reduced it to a trivial snoar. apologies to those who bored to tears.
asciilifeform not intended 'verisimilitude flavour'
shinohai[busybot]: TP opus meum bunghole
phf[asciilifeform]: http://logs.nosuchlabs.com/log/pest/2022-12-25#1019348 << but on the other hand we don't want to discourage you writing experimental code, because unlike athena born as she was from the forehead of her father, distributed code has too much emergent behavior to attempt to reason it from first principles
dulapbot: Logged on 2022-12-25 12:47:42 asciilifeform: starts to think that in the process of posting this, reduced it to a trivial snoar. apologies to those who bored to tears.
asciilifeform: phf: per asciilifeform's pov, when writing field-expedient sadlang proggy, best one can do is to keep it small & correct, so to 1day rewrite
asciilifeform: that being said, aint aboutta post erry cpp fart, except as to discuss algos
phf[asciilifeform]: fwiw the code can be implemented as is in pest.lisp, because iit's intentionally not threaded and event based, including the 1s tick `periodic` funcion that does useful work
asciilifeform: phf: asciilifeform's current attempt is forcibly threaded (on acct of the gui), and so decided that may as well properly bring out blackpacket eating to worker thrds, the redpacket processor -- 'consumer', etc
asciilifeform: ( fwiw line-rate packet-eatin' reqs max parallelization )
asciilifeform currently gnashing teeth re guiism idjicies -- e.g. on crapple, text entry box never gets default focus when displayed, no matter how baked, and nobody anywhere seems to know why
asciilifeform has a rather 'half gui', where there's a widget that can display msgs in arbitrary order, and anuther 'tab' that displays console 'shell' through which 'peer x', 'key x key', etc. which actually control the proggy
phf[asciilifeform]: 􏿽http://logs.nosuchlabs.com/log/pest/2022-12-25#1019359 << community consensus™ waivers on this point. i'm of twisted python school, and also did my time in realtime bidding in java saltmines where fixed ns to respond requirements were achieved exclusively with kevens on fds non-p
dulapbot: Logged on 2022-12-25 13:01:49 asciilifeform: ( fwiw line-rate packet-eatin' reqs max parallelization )
phf[asciilifeform]: 􏿽arallel code, so i'm suspicious of max parallelization argument. though some modern™ approaches which have awareness of thread switching granularity and cache effects and modern™ architectures all rolled into one allegedly can outperform
asciilifeform: phf: feel free to check asciilifeform's napkin calculations re subj
bitbot[asciilifeform]: (asciilifeform) 2021-09-23 asciilifeform: i expect you'd have at least 8cores on reasonable box, which gives you ~105840 ticks to process a packet, imho entirely doable.
asciilifeform: seems clear that gb/s pestronics aint happening on 1 cpu core, no matter what kinda cpu.
asciilifeform: eating blackpackets in parallel dun require anyffin 'modern' in re threading; is 'embarrasingly parallel'(tm)(r)(cray) sorta job
asciilifeform: ( and also recall that the bigger the wot, the linearly moar work is to verify a blackpacket )
jonsykkel[asciilifeform]: after thikning about ur system with linked list and decent implementaiton, i agre my algo is bloat and trash
jonsykkel[asciilifeform]: wastes ~2x memory
bitbot[asciilifeform]: Logged on 2022-12-25 10:49:21 asciilifeform[6]: http://logs.bitdash.io/pest/2022-12-25#1019254 << a cpp11ism
jonsykkel[asciilifeform]: http://logs.bitdash.io/pest/2022-12-25#1019276 << luby frags will go in filter? this is imposible imo, if want to send fat warez at >dialup speed
bitbot[asciilifeform]: Logged on 2022-12-25 11:03:13 asciilifeform[jonsykkel]: observe that filter stores hashes of all msgs, not only chained; and emitted as well as received. letting'em all sit for potentially 15 extra min. is mega-bloat, esp. after we have signpost's luby
dulapbot: (asciilifeform) 2022-07-25 asciilifeform: jonsykkel: there's no particular reason to dedupe warez fragments by looking in the db (or ever placing'em there to start with)
asciilifeform: jonsykkel: filter never touches disk (unless, i suppose, yer on a 20+yo machine where swapping is a thing )
asciilifeform: jonsykkel: filter is absolutely req'd, per the dictum that no packet is to ever be processed 'as-new' >1nce; and in particular, in 0xfa draft, there are binary packets where no speaker field;
asciilifeform: ... and the only way you can distinguish -- in the event a buggy station (or joker replaying captured packets) throws it back at you -- one you sent from one addrs'd to you -- is the filter
asciilifeform: ( per new spec -- anyffin you send, chained or not, hits the filter before it hits the wire )
asciilifeform: at the risk of pedanticism -- only ~chained~ msgs go to db on disk.
jonsykkel[asciilifeform]: asciilifeform: yes, its in memory, where it will be imposibly big is my point, if its to store every luby frag
jonsykkel[asciilifeform]: store hash of, that is
asciilifeform: jonsykkel: you dun have to get it let 'impossibly' big (tho what do 15min of 32byte hashes of messages coming at 1g/s weigh? prolly coupla GB at most)
asciilifeform: jonsykkel: ... instead can cap it, and start ignoring incomings until space frees
asciilifeform: but having the deduper aint optional, if you accept 'not dupe' on faith at ANY point, yer open to replays
asciilifeform: note that randos can't fill yer dedupe filter (it only stores hashes of validated, i.e. from actual peer, incl. self, and ~not previously seen~ msgs)
asciilifeform: the most that can be done by rando replayer is to capture e.g. MB of legit packets and play it back to you until its timestamps expire. (which won't grow the filter, as they'll be dupes)
asciilifeform: in other words, filter simply contains hashes of ~15min (avg) legit traffic in both dirs.
asciilifeform: jonsykkel: at ~226860 pest packets/s ( see here ) , and 32min worth ,
bitbot[asciilifeform]: (asciilifeform) 2021-09-23 asciilifeform: PeterL: let's assume ethernet. so, in bytes, let's calculate 1 packet's mass: 5 (gap) + 4 (preamble) + 14 (eth header) + 20 (ipv4 hdr) + 8 (udp header) + 496 (pest) + 4 (ethernet crc) == 551
asciilifeform: ... and 32 byte per (hash), 32 * 60 * 30 * 226860 / (1024**2) == ~12462 MB max. (not incl. overhead of the set mechanism)
asciilifeform: ( tho in practice you prolly won't be eating at 1g/s on yer box, the hmac thing will be bottleneck )
bitbot[asciilifeform]: Logged on 2022-12-25 13:25:58 asciilifeform[5]: ( and also recall that the bigger the wot, the linearly moar work is to verify a blackpacket )
asciilifeform: *30 min worth
asciilifeform: if one were to narrow the time window to +/- 10min instead of 15 -- ~8.3GB, moar manageable
asciilifeform: but in either case certainly not 'impossible' imho
jonsykkel[asciilifeform]: the overhead of set mechanism as far as i can tell will double that number
jonsykkel[asciilifeform]: then u gota traverse those (max) 200k long lists and delete 200k/sec from set (presumably hash table) as stuff starts expiring
jonsykkel[asciilifeform]: maybe not "imposible" but significant, imo
jonsykkel[asciilifeform]: conclusion from last linked thread was iirc no reason to put frags in filter cuz replays of these wont have any effect
asciilifeform: jonsykkel: depends on what sorta encoding used for the frags, neh
asciilifeform: for 1 thing, there's no 'speaker' field in'em, so x->y can be passed back to x and he'll think is from y (if he hasn't got it in his filter) and vice-versa
asciilifeform: for anuther thing, luby per se (even signpost's variant) doesn't automatically tolerate garbage
asciilifeform not knows of 1 that does
asciilifeform: naturally it tolerates missing/outta order frags. but not random piss (e.g. replayed from prev. sessions)
dulapbot: (asciilifeform) 2022-07-25 asciilifeform: each luby msg would include hash of the slice it is a frag of. thereby dr.evil piping in chunks of previous transfers would do 0
jonsykkel[asciilifeform]: which does appear to tolerate random piss
asciilifeform: jonsykkel: is how asciilifeform handled multipart chains, yes
asciilifeform: jonsykkel: how about e.g. header packet tho, where one requests transmission of a file.
asciilifeform holds that in general a station oughta always know 1) whether arbitrary msg is previously unseen 2) whether it had been sent by station itself or by a peer. 1+2 appears to require 'all goes in filter' in the general case.
jonsykkel[asciilifeform]: indeed would have to be restricted to the data fragments strictly
jonsykkel[asciilifeform]: agree that would be nice and simple, but at cost of 4 xtra ram sticks
asciilifeform: if filter skips specifically unchained direct msgs of types which tolerate dupes cleanly, then imho acceptable
asciilifeform: (ugly but acceptable, not errybody has 256GB of stix installed )
asciilifeform: problem is that sumbody can eat yer cpu 100% by replaying luby frags, tho
asciilifeform: key intent of pest is that a station can be made as ddos-proof as the external net pipe(s) allow.
asciilifeform: if can guarantee that a replayed luby frag is rejected as fast (or faster) as the filter would've -- then, worx
jonsykkel[asciilifeform]: posible, hard to say which is worse, jumping around randomly in memory 100k's per sec to delete from filter set is not great
asciilifeform suspects that replayed lubyism could be rejected faster than a lookup in 16GB+ heap
asciilifeform: re 'how' will prolly have to wait until the lubytron actually specified.
asciilifeform: for thread-completeness, anuther solution could be to actually track clock diff. b/w you and $peer, and treat binary msgs as expiring in e.g. 1min from timestamp (adjusted for the diff) rather than 15.
asciilifeform: ( for arbitrary msg, +/-15min is forced by 'no guarantee that clocks are synced, gotta be able to speak if they aint' but for rapid-fire sequence of msgs, this aint a concern, the clocks won't drift on time scale of minutes or even hours by any substantial amt
asciilifeform: you'd still be eating the cpu cost of working the filter heap, but in this case of over9000x smaller one.
asciilifeform: ( if we suppose that under no reasonable circumstances will a packet >~1min. old in physical time need to be considered legit)
asciilifeform: ... if someone sets up a pestron on mars, will need to revisit this, lol. but until then, imho entirely feasible to say 'msg is valid for 1min of physical time'
asciilifeform: so, to run with this, suppose that 1) msg from cold peer (i.e. 1 that hasn't transmitted for $interval) is valid in +/-15m window 2) msg from 'warm' peer is valid for 1min (following drift-adjusted timestamp)
asciilifeform: (1min may even be excessively generous. ever seen a 1min ping time?)
asciilifeform: ^ jonsykkel awt phf signpost et al ^ plox to comment.
jonsykkel[asciilifeform]: heap would be smaller, memory problem less bad, but same # of ops for cpu
asciilifeform: jonsykkel: not same, as patently stale (per timestamp) msg only gets hash-compared to list of active getdata's, and not touched the filter
asciilifeform: no need to look in the filter if can throw out as stale.
asciilifeform: the +/-15min for ~all~ msgs, on reflection, is lunacy imho
asciilifeform: it only makes sense if you've gone at least coupla hrs b/w last contact with $peer
jonsykkel[asciilifeform]: right, not same for stales, but common case during lubytronic activities is that u are blasted with valid packets
asciilifeform seen ping times in the range of coupla sec., when over ancient 'slip' etc., but nuffin remotely approaching 1min
jonsykkel[asciilifeform]: maybe can be achieved with tcp tunnel
asciilifeform: imho if you have ~1min pings and you aint operating a space fleet, you have serious problems that oughta be dealt with before trying to operate pestron
asciilifeform: ( pestron is not intended for 'sneakernet', carrier pigeon, etc. systems )
asciilifeform: if yer sneakernetting, send pgpgrams.
asciilifeform must bbl
jonsykkel[asciilifeform]: will have to shelve my plans of martian carrier pigeon experiments
shinohai[busybot]: $ticker btc usd
busybot: Current BTC price in USD: $16823.9
shinohai[busybot] views bot latency times .... "I'm ok with dat!"
asciilifeform currently thinking: 1st packet from cold peer -- +/-15min; packet from warm peer valid +/- 15sec (after getting drift delta from the 'uncolding' packet). would need to think how behaves under replay scenario tho
asciilifeform: i.e., theoretically, someone could replay an 'uncolding' old packet within 15min of its expir, and throw in the rest, and some of'em will be seen as fresh (given as they were evicted from filter)
asciilifeform: needs moarthought imho.
phf[asciilifeform]: 􏿽http://logs.nosuchlabs.com/log/pest/2022-12-25#1019365 << that's five hits of grateful dead grade acid level of architectural space man calculations. they look correct, and possible provide reasonable reference limits on things, but considering that you're posting sample code tha
dulapbot: Logged on 2022-12-25 13:21:39 asciilifeform: phf: feel free to check asciilifeform's napkin calculations re subj
bitbot[asciilifeform]: (asciilifeform) 2021-09-23 asciilifeform: i expect you'd have at least 8cores on reasonable box, which gives you ~105840 ticks to process a packet, imho entirely doable.
phf[asciilifeform]: 􏿽http://logs.nosuchlabs.com/log/pest/2022-12-25#1019365 << that's five hits of grateful dead grade acid level of architectural space man calculations. they look correct, and possible provide reasonable reference limits on things, but considering that you're posting sample code that
dulapbot: Logged on 2022-12-25 13:21:39 asciilifeform: phf: feel free to check asciilifeform's napkin calculations re subj
bitbot[asciilifeform]: (asciilifeform) 2021-09-23 asciilifeform: i expect you'd have at least 8cores on reasonable box, which gives you ~105840 ticks to process a packet, imho entirely doable.
asciilifeform: oh hm phf is that a duped msg or local station oops ?
phf[asciilifeform]: and the other question is, where's the rest of it?
asciilifeform: phf: seeing same item on desk as visible in billymg's logger
phf[asciilifeform]: 􏿽uses c++ std, and i'm writing common lisp, we're not even in the same u.s. state as the building which has a room, where the practical conversation about this grade of solution takes place.
phf[asciilifeform]: ah yeah i see it on billymg's logger also. not on nosuchlabs. maybe eventually?
asciilifeform: phf: re the visible paragraph -- afaik 'max packets/sec can enter via a gb/s nic?' is hard bound; but the rest of thread is obv. dep. on internals of filter
bitbot[asciilifeform]: (asciilifeform) 2021-09-23 asciilifeform: PeterL: let's assume ethernet. so, in bytes, let's calculate 1 packet's mass: 5 (gap) + 4 (preamble) + 14 (eth header) + 20 (ipv4 hdr) + 8 (udp header) + 496 (pest) + 4 (ethernet crc) == 551
asciilifeform: (i.e. obv. nobody -- or certainly not asciilifeform -- knows how much the cppistic heap weighs when stuffed fulla x hashes, then y deleted, etc )
asciilifeform: prolly depends on phase of moon, whether jupiter aligned with mars, gcc version, etc. rubbish.
asciilifeform: the same, unfortunately, is true of ada's equiv. to this datastructure
asciilifeform: 'hash maps' aint intended, apparently, for people who truly giveafuck re precise # of bytes occupies. (these -- write own structure, and not resort 'like lamer' to what comes with compiler)
phf[asciilifeform]: `we wrote own equivalents of following c++ std libs to support necessary hard guarantees` etc.
asciilifeform: so phf 100% correct, no hard bounds avail. nor likely to be until thing is reimplemented 'ffa-style'
asciilifeform skeptical even re bounds of a commonlisp variant, if there's any consing happening at all
asciilifeform recalls in '15 when went on a lengthy chase re 'why trb hashmap grows unboundedly'
phf[asciilifeform]: 􏿽common lisp solution is to refine the algo from naive and elegant to tight an heavily annotated, but mostly give up somewhere half way in once you discover that everyone still mostly uses the protocol to send text messages at 1message/minute to a group of 10 friends. end up outperf
phf[asciilifeform]: 􏿽orming all competitors at this particular task.
asciilifeform: asciilifeform's concern is when 1 or more of the 10 start shooting multi-GB luby pissstreams to 1 anuther
asciilifeform: btw revisiting cppistic hashmaps -- they're retarded in moar ways than 1 (tho in some cases theoretically fixable). for instance, defaults to actually hashing (unsurprise) the inputs, even when, as in our case, is already a fixed-length hash
phf[asciilifeform]: crashing the one canonical python implementation and bring the whole network down
asciilifeform: ( theoretically overridable w/out resorting to compiler-proprietary gnarl. but not tried yet )
asciilifeform: phf: atm even that 'send erryone a % command to run' lolbug still standing
phf[asciilifeform]: 􏿽i'd probably put theoretical future luby code into a separate conditional branch, have totally special caching etc. strategy for the messages. at which point the problem of black->red as fast as possible becomes most important, and there's plenty of work even there. maybe ffi to so
phf[asciilifeform]: 􏿽me c lib, maybe write an avx vectorized version, etc.
asciilifeform: asmistic hmac384 would be an obvious win imho
asciilifeform: ditto serpent
asciilifeform has a half-written x64 serpent sitting around for yrs
asciilifeform: for thread-completeness, there's of course the obvious mega-cheat where one actually looks at the ip from which got the packet, and try the last-good key 1st, rather than rando-rotating through wot. but asciilifeform in the past explained wai 'is cheat', and 'forbidden in spec'
asciilifeform: ( it blows away ability to compute worst-case performance, i.e. under flood of martians )
asciilifeform: ( as well as making it easier for third party to distinguish station processing a martian from where processes a valid packet, via time sidechannel )
asciilifeform: and ftr, the other thing -- pest is intended to be usable with radio, where no such thing as 'origin ip'.
asciilifeform: ( i.e. errybody transmits to errybody )
asciilifeform: this is atm 'bridge too far', but 'can't throw a word out of a song'(tm)
asciilifeform: the radio not yet built, and who knows if/when. but wainot simulate the computational pain ~nao~, so not find a surprise later, 'we've the radio, but no one has fast enuff cpu to actually use it'
asciilifeform not eager to preside over a repeat of his earlier moronic 'surprise' where 'no pc is fast enuff to 4096-bit rsa with arbitrary exponents at gb/s linerate'
← 2022-12-24 | 2022-12-26 → ↑
Random(pest) | Download hourly DB snapshot | Get Source Code