00:22:36 -!- arseniiv has quit (Ping timeout: 265 seconds).
00:50:17 -!- normsaa has quit (Quit: Client closed).
00:50:24 <esolangs> [[User talk:Fmbalbuena]] M https://esolangs.org/w/index.php?diff=88035&oldid=87892 * Fmbalbuena * (-28)
01:06:21 -!- delta23 has quit (Quit: Leaving).
01:43:28 <imode> are there any data structures that are like a trie but aim for compressing really wide trees vs. very deep ones.
01:45:49 <zzo38> I don't know of any.
01:46:49 <Corbin> Isn't one of the lemmas leading to Huffman's encoding basically a proof that trie alphabet size doesn't matter asymptotically? (So that the alphabet size should be tuned, as in B-trees.)
01:51:06 <zzo38> I don't know what those lemmas are, but I can see how it might make sense with such a question
01:52:10 <Corbin> I only dimly remember. Something about how alphabet size ends up in the base of a logarithm, which is then washed away with a big-O.
01:52:37 <shachaf> What sort of data structure should you use for an ordered key-value map that doesn't need to be modified?
01:53:21 <Corbin> Insertion-ordered or ordered by key comparison? Or IOW custom traversal order?
01:53:24 <shachaf> B-trees seem like a natural answer -- maybe B-trees with nodes biased toward completely full if possible, rather than up to half-empty -- but is there something better?
01:53:32 <shachaf> I mean ordered by key comparison.
01:54:32 <Corbin> B-trees/HAMTs are where I would start research.
01:54:58 <shachaf> Isn't HAMT unordered, since it's based on hashing?
01:57:40 <imode> Corbin: I should be more specific: I'm compressing lists of string rewrite rules by throwing them in a trie, only to realize that the actual trie will be very wide. my intent is building a format for these tries to be loaded and read (no modification after the fact).
01:57:54 <shachaf> Speaking of hash tables, how about this idea for hash tables without linear-time resize behavior:
01:58:07 <shachaf> You reserve the maximum amount of addres space up front, but only use a little bit of it at first.
01:58:33 <shachaf> To double the hash table, you double the amount of committed memory, but still keep entries where they are.
01:58:52 <shachaf> Then you incrementally start moving entries over to the "right" spot in the new region as you do more operations.
01:59:23 <shachaf> Before that's done, lookups that land in the new region have to check the old region too.
01:59:30 <shachaf> Do people do that sort of thing?
01:59:34 <imode> I could use huffman encoding, but because the interpreters that deal with these rules need to have a common symbol table to "latch" on to to do things like I/O, it won't be easy, as the reserved symbols could change their encoding relative to how they're used in the rule set.
01:59:41 <Corbin> imode: You could steal a technique from the ordered-by-default doubly-indirect hashtables used in Python and a few other Smalltalk relatives. Each rewrite rule probably only uses a small number of tokens in total, right? It's only the entire dictionary that's big.
02:00:06 <imode> https://slack-files.com/T0191PWV41E-F02EC4E66P6-aceccd9554
02:00:26 <imode> here's a compiled trie from a ruleset that deals with stacks and unary math.
02:00:38 <shachaf> Oh, all I needed to do was thinking of the word "incremental", and look up hash table incremental resizing.
02:00:39 <Corbin> So you could put the dictionary into a single global array and also put indices from that global array into a rule-specific local array. Then compress the trie relative to the local array instead of the global array.
02:01:45 <imode> not sure I follow, but another way to approach it would be to simply supply auto-generated mappings for each of the reserved symbols on every compilation.
02:01:48 <Corbin> I'm not explaining it well; here's a better explanation: https://www.pypy.org/posts/2015/01/faster-more-memory-efficient-and-more-4096950404745375390.html
02:03:49 <imode> I've got to step away for a bit, but were you the one that I handed the 500MiB dot file containing a mandlebrot renderer in string rewriting rules transpiled from BF?
02:04:32 <Corbin> No, although (1) that sounds *hilarious* and (2) I definitely have generated DOT files around that size.
02:50:09 <imode> back. yeah it's uh, ugly af.
02:52:47 <zzo38> With what I have, I might need to sort a linked list (although there might be another way).
03:00:00 -!- Taneb has quit (Quit: I seem to have stopped.).
03:01:07 -!- Taneb has joined.
03:01:07 -!- Cale has quit (Ping timeout: 252 seconds).
03:10:20 -!- Cale has joined.
04:06:03 -!- mla has quit (*.net *.split).
04:06:04 -!- dnm has quit (*.net *.split).
04:06:05 -!- Soni has quit (*.net *.split).
04:06:05 -!- ski has quit (*.net *.split).
04:06:12 -!- ski has joined.
04:06:36 -!- Soni has joined.
04:06:53 -!- dnm has joined.
04:10:44 -!- ski has quit (Ping timeout: 265 seconds).
04:20:16 -!- esolangs has joined.
04:20:16 -!- fizzie has joined.
04:20:18 -!- ChanServ has set channel mode: +v esolangs.
04:20:59 -!- Deewiant has joined.
04:28:03 <esolangs> [[Special:Log/newusers]] create * Aidenbc * New user account
04:31:41 <esolangs> [[Esolang:Introduce yourself]] https://esolangs.org/w/index.php?diff=88036&oldid=88006 * Aidenbc * (+191) /* Introductions */
04:31:58 -!- jryans has joined.
04:50:50 -!- Trieste has quit (Ping timeout: 260 seconds).
05:10:13 -!- sprock has joined.
05:40:40 -!- hanif has joined.
05:41:52 <hanif> <shachaf> What sort of esolang is this? https://cs.nyu.edu/pipermail/fom/2021-September/022861.html => cool thanks for sharing
05:56:56 <hanif> wow martin davis is the moderator for the mailing list
06:17:12 -!- hanif has quit (Ping timeout: 276 seconds).
06:18:44 <esolangs> [[SUB]] N https://esolangs.org/w/index.php?oldid=88037 * Hakerh400 * (+5521) +[[SUB]]
06:18:48 <esolangs> [[Language list]] https://esolangs.org/w/index.php?diff=88038&oldid=87951 * Hakerh400 * (+10) +[[SUB]]
06:19:04 <esolangs> [[User:Hakerh400]] https://esolangs.org/w/index.php?diff=88039&oldid=87722 * Hakerh400 * (+10) +[[SUB]]
06:26:52 <esolangs> [[SUB]] https://esolangs.org/w/index.php?diff=88040&oldid=88037 * Hakerh400 * (+16)
06:28:12 <esolangs> [[SUB]] https://esolangs.org/w/index.php?diff=88041&oldid=88040 * Hakerh400 * (+2)
06:44:30 -!- hanif has joined.
07:18:28 -!- Sgeo has quit (Read error: Connection reset by peer).
07:25:24 -!- tromp has joined.
07:34:42 -!- immibis has quit (Ping timeout: 265 seconds).
07:47:48 <b_jonas> shachaf: for an ordered key-value map? a sorted array generally, if it fits within the RAM
07:50:22 <shachaf> b_jonas: Surely something like a B-tree is better than a sorted array.
07:50:37 <shachaf> Binary search on a sorted array makes pretty bad use of cache.
07:50:58 <b_jonas> shachaf: it isn't really because you're always starting to compare with the same elements, so those stay in the cache
07:51:14 <b_jonas> just make sure it's not power of two sized so you don't get stupid cache collisions
07:51:28 <b_jonas> nor anything close to power of two
07:52:50 <b_jonas> perhaps pad it out to fibonacci sized by padding with infinities on an end or something
07:53:04 <b_jonas> do you have variable key sizes or fixed?
07:53:54 <b_jonas> hmm no, probably not fibonacci
07:59:17 <nakilon> -- do you have a clue in DB indexing? -- yeah, I've implemented indexing -- what?! -- ...
08:01:10 <nakilon> -- I saw "DevOps" in your CV, what devops tools do you use? -- I use no tools, devops is a methodology... -- what?! -- ...
08:02:08 <nakilon> -- what hobbies do you have? how do you have fun? -- I made an esolang -- what?!
08:06:11 <b_jonas> sorry, I'll need to think about what size you should use for cache-friendliness (still it the table fits in RAM)
08:06:18 -!- hendursa1 has joined.
08:06:21 <b_jonas> somehow I never thought about that, even though it is an important enough basic question
08:08:31 <b_jonas> so thanks for the question actually
08:08:42 <b_jonas> (RAM vs disk matters here because their caching differ)
08:09:00 -!- hendursaga has quit (Ping timeout: 276 seconds).
08:19:09 * nakilon has already borrowed money from two people to survive in this stupid world that can't give a job
08:20:39 <shachaf> b_jonas: But you're wasting a whole cache line on one element.
08:20:47 <shachaf> Rather than using the entire root of the B-tree.
08:57:45 -!- hanif has quit (Ping timeout: 276 seconds).
08:59:29 -!- ais523 has joined.
09:02:00 <ais523> <shachaf> What sort of esolang is this? https://cs.nyu.edu/pipermail/fom/2021-September/022861.html ← that's almost literally Thue (the version which is nondeterministic in the mathematical/declarative sense rather than the randomness sense), the only difference is in the startup state and a different model for halting
09:02:59 <ais523> actually, if you think of the operands of R being the other way round, there isn't even a difference in the startup state, "is this string in GEN(R)" becomes equivalent to "can this Thue program reach the empty string and halt?"
09:03:06 <ais523> (so the "reach the empty string and") is the difference
09:03:17 <ais523> oh, also it's limited to an alphabet of {0,1} but this doesn't matter for Thue at all
09:03:51 <ais523> <fizzie> I do like sudo's "This incident has been reported to the authorities" message. ← I actually received one of those reports once (after typoing my password in sudo one too many times), I was shocked it actually went somewhere
09:04:17 <ais523> apparently it just sends local email to root, so it depends on whether you have an email stack that a) understands local email and b) has root's mailbox linked up to something
09:06:27 <ais523> b_jonas: the funny thing about the power-of-two sizes is that they're sometimes the worst size but sometimes the best size, depending on the exact algorithm you're using
09:07:30 <ais523> there are two basic problems, false aliasing (some parts of modern processors speculatively assume that if the bottom few bits of addresses match they'll be the same as each other, and need to rewind if htey turn out not to be)
09:07:57 <ais523> and the fact that modern caches are effectively lossy hash tables and if you find collisions in the hash function, they'll end up losing a lot more data than they should
09:08:21 <ais523> that said, I think the hash functions powering the caches are generally non-public, and more complex than "bottom N bits"
09:08:26 -!- wob_jonas has joined.
09:08:49 <wob_jonas> shachaf: sorry, let me try to give a better answer to this\
09:10:18 <wob_jonas> so basically this question is complicated because the ugly real world comes in, and the full answer is probably more or less to read the entire future third edition of TAOCP third volume.
09:10:47 <ais523> the main culprit for false aliasing is read-after-write, if you write 0x5000000 and then read 0x5001000 some processors will delay the read until after the write because it cautiously assumes that they might overlap
09:10:57 <velik> The Art of Computer Programming -- series of tomes by Donald Knuth https://en.wikipedia.org/wiki/The_Art_of_Computer_Programming
09:11:35 <wob_jonas> first, in the unrealistic case when you have fixed size keys that are so opaque you can only compare them, yet they are fast to compare, then here's what you want\
09:11:58 <ais523> so, power-of-two sizes are good if you're reading one element and then writing the corresponding element, because that gives you a guaranteed write-after-read (which doesn't stall) and reduces the chance of a read-after-write randomly happenign with some other pair of addresses
09:12:07 -!- Robdgreat_ has changed nick to Robdgreat.
09:12:15 -!- Robdgreat has changed hostmask to ~rob@user/robdgreat.
09:13:22 <wob_jonas> make a sorted vector, pad it to size that's a power of r minus one where each cache line can fit r-1 keys, do the search with r-way comparisons so you effectively traverse a complete r-ary tree, but without pointers because the fixed size keys let you elide all the pointers.
09:13:51 <wob_jonas> you can permute the cache lines, and sometimes you have to to avoid a really bad L1 cache pattern, but most arrangements are good enough:
09:14:20 <nakilon> in all usual programming languages code is 1-dimentional; in many esolangs it's 2 or more dimensional; but all those "lines of code" are parallel; there should be a language with no parallel lines
09:14:31 <wob_jonas> eg. the case that's really bad is a binary tree (one key per cache line) that's exactly power of two plus one size;
09:14:53 <wob_jonas> a permutation that's probably good enough is to just place each level of the tree contiguously and one after another
09:15:02 <nakilon> some code notation that would have the "code" either lined up randomly or along the curves
09:15:50 <wob_jonas> if you don't want to just find the first key less than your query key, then can use any permutation; if you want to access some subsequent nodes after each query then you want to permute as little as possible
09:16:21 <wob_jonas> for a binary tree (one key per node) I think you can get away with a sorted vector that's size 2**n/63, and I know that sounds sillyi
09:16:45 <wob_jonas> now the problem is that the case when your keys are fixed size and opaque yet you can do fast ordered comparison is unrealistic
09:17:45 <wob_jonas> because if you can do fast ordered comparisons and want an ordered structure, then you may also be able to do arithmetic on the key and do the sort of accelerated search where if your query starts with Z then you go to the last 1/26 of the book
09:18:07 <wob_jonas> but the good news is, in practice unless your distribution is even, I don't think this helps too much, and just an r-ary tree works well enoguh
09:18:17 <esolangs> [[Talk:Mogus]] https://esolangs.org/w/index.php?diff=88042&oldid=87976 * ArthroStar11 * (+247)
09:18:46 <wob_jonas> by the way there's an unlikely exception from this, which is when you have prior information about the distribution of your queries and they're VERY skewed, like the query is always the same fixed word, and in that case you can do better, but this is rare\
09:19:21 <wob_jonas> if your comparisons are very slow, then you want a binary tree, or fibonacci tree if you can only do 2-way comparisons, because you're dominated by the comparisons and the memory access doesn't matter,
09:19:44 <wob_jonas> but you may have a comparison speed in between the two which is one of the ugly real world parts
09:19:51 <wob_jonas> now all this so far was about fixed size keys
09:20:06 <wob_jonas> in reality if you need an ordered structure, you are more likely to have variable sized keys
09:21:23 <wob_jonas> if your key sizes are variable, then you still want a complete tree with each node branching one plus as many ways as many keys you can fit to the cache line (or page on a disk), but this number of branches can differ in each node
09:21:39 <wob_jonas> this is similar to a b-tree, but you may be able to do somewhat better,\
09:21:56 <wob_jonas> because if you don't have to modify your structure, then you may be able to encode your pointers somewhat more efficiently
09:22:52 <wob_jonas> as in, if each level of the tree is stored in a sorted order, then the first few levels can already tell you the first bits of the pointers on each of the subsequent levels, so you needn't encode those bits in all the later nodes
09:23:30 <wob_jonas> this ends up in an ugly tradeoff between memory access speed versus computation speed, so it's hard to tell how much you want to compress those addresses and how exactly\
09:23:55 <wob_jonas> typical real world optimization problem where you won't get a once and for all simple theoretical solutino
09:25:55 <wob_jonas> also an ugly part is, even in the fixed size, that if your tree is large enough but still within memory, then you may want nodes larger than a cache line, beacuse you may be able to read from memory faster if it's adjacent cache lines,
09:26:14 <wob_jonas> but how exactly the caches and memory work in this respect I admit I don't understand, so I can't tell what you actually want to do
09:29:00 <wob_jonas> so sadly this is the kind of hard problem where the final TAOCP edition will help us a lot\
09:29:37 -!- hanif has joined.
09:32:03 <wob_jonas> and it's hecking far in the future because it's volume 3
09:33:29 <wob_jonas> I got the sudo message (in local email inbox to root, on the workstation that doesn't normally handle emails) lots of times
09:33:56 <nakilon> if humanity make an elixir of longer life they should give it to Knuth
09:34:16 <wob_jonas> "the funny thing about the power-of-two sizes is that they're sometimes the worst size but sometimes the best size, depending on the exact algorithm you're using" => yeah. I did a lot of bitmap image processes, where my rule of thumb is to make rows a size in bytes that is 64 modulo 128
09:34:48 -!- hanif has quit (Ping timeout: 276 seconds).
09:35:01 <wob_jonas> ais523: the hash function of the L1 cache is the bottom 12 bits (of the address of bytes) by necessity on x86,
09:35:14 <velik> Result: 83 years 8 months 3 days
09:35:16 <wob_jonas> and there's always 8 cache lines per fixed bottom of 12 bits
09:35:56 <wob_jonas> this is by necessity because the L1 cache has to be so fast (within very few clock cycles) that it needs to select the cache line before the linear address translated by the cache table to physical address is known,
09:36:46 <wob_jonas> and x86 can have 2**12 byte sized pages, with no architectural way that all pages are larger, so you can't use more than 12 bits of the address;
09:37:22 <wob_jonas> and the same page can be mapped to multiple linear addresses (whether within the same process or different processes) and often will be, so you can't just cache by linear address and roll back everything if that goes wrong
09:38:10 <wob_jonas> all this applies ONLY to the L1D and L1C caches, of which there's one per CPU core, no other cache I think
09:38:16 -!- hanif has joined.
09:39:04 <wob_jonas> you may be right that the hashing methods of some of the caches aren't known, but because those caches are slower, they can also do more elaborate things and so it's harder to accidentally stumble into a bad pattern just by choosing the wrong address
09:42:51 <wob_jonas> by the way this means that the L1D cache is always 32k size in any modern x86 cpu
09:43:18 <wob_jonas> while the size of the L2 cache and L3 cache varies widely depending on how much you pay
09:43:59 <int-e> haha. "should not be depicted with a zipper mouth"
09:44:30 <int-e> (character details for that one... can HackEso display character details?)
09:45:54 <wob_jonas> int-e: https://unicode.scarfboy.com/?s=U%2b1F62C , which parts do you want? they won't all fit into an IRC message
09:46:46 <wob_jonas> plus you also need to follow the "PDF on unicode.org" link, here to http://www.unicode.org/charts/PDF/U1F600.pdf
09:47:37 <wob_jonas> because that PDF is what has the comments like that zipper mouth thing
09:47:47 <wob_jonas> and the see alsos to other characters, which is often useful
09:48:02 <int-e> wob_jonas: the "comments", https://www.fileformat.info/info/unicode/char/1f62c/index.htm
09:48:19 <int-e> (the former doesn't work for me, says the code point is unknown?)
09:48:26 <int-e> (maybe some javascript requirement)
09:49:17 <wob_jonas> yaeh, it doesn't work for some reason
09:49:39 <int-e> it was helpful enough to provide further links
09:50:00 <wob_jonas> I think the maintainer did some changes to the page and broke some things temporarily
09:50:08 <wob_jonas> IIRC there was a message to that effect
09:50:23 <fizzie> I've always been annoyed by the fact that UnicodeData.txt doesn't include those comments. But they're in NamesList.txt of the UCD.
09:50:28 <wob_jonas> yeah, "Notice: I'll be updating the information in the next weeks. It'll be broken occasionally." that's been there for months but you know how that goes
09:50:57 <int-e> Anyway, I found this particular comment funny. So specific...
09:51:47 <wob_jonas> I generally don't care about all the ininite smiley faces and other emoticons added
09:52:11 <wob_jonas> the only smiley faces that matter are the ASCII ones like :-) and the two in cp437
09:54:20 <int-e> wob_jonas: I'm not studying the smileys; sometimes I encounter a smiley on Twitter that I don't understand and care enough to look it up.
09:55:16 <int-e> Oh and in the meantime I'm waiting for Unicode modifiers to become accidentally TC. ;)
09:55:28 <wob_jonas> .oO("hmm, is that smiley supposed to be a zipper mouth? let me look it up in the unicode database.")
09:56:27 <wob_jonas> "Unicode modifiers" => I think the bidirectional rendering and line breaking algorithm might get TC first
09:56:34 <int-e> I imagine that it works as advice to font designers... who really have to go through unicode points one by one
09:56:34 <ais523> <wob_jonas> by the way this means that the L1D cache is always 32k size in any modern x86 cpu ← there are some that advertise "64k per core", I wonder if the hyperthreads have separate L1 caches?
09:57:28 <wob_jonas> ais523: are those x86 cpus, and are you sure it's not the L2 cache of a cheap cpu? I'd like to see this
09:58:42 <int-e> ais523: that strikes me as silly? except maybe as a separation feature, where you (optionally) tag entries by hyperthread in a way that they map to different cache sets
09:59:00 <ais523> wob_jonas: AMD Ryzen 9: https://www.amd.com/en/products/cpu/amd-ryzen-9-3900x
09:59:19 <ais523> 64KiB of L1 cache per core, but 32KiB per hyperthread
09:59:32 <ais523> oh, it's combining L1C and L1D
09:59:34 <ais523> sorry for the false alarm
09:59:43 <ais523> that's sneaky, adding the two together
09:59:58 <int-e> ais523: I mean, I don't know... it's just so opposite to the core idea behind hyperthreads as I understand it, which is to have a single core but fill its idle time by keeping track of two PCs and register sets.
10:00:26 <wob_jonas> I mean sure, both L1D and L1C are very important, but they're separate caches, and they're separate partly because each can only be 32k so this way you get 32k each instead of 32k total
10:00:31 <ais523> int-e: it'd be plausible to use "hyperthread on which we accessed this" as an extra bit of address, I guess
10:01:02 <int-e> ais523: in particular you'd want to be able to use the full cache when hyperthreads are disabled...
10:01:29 <wob_jonas> ais523: I don't think you can do that in L1. you could in theory have two separate L1 caches, but that gets very close to not being hyperthreading but two separate cores, so it's sort of poinless, takes away the point of hyperthreading
10:02:29 <wob_jonas> or, cynically speaking, the people who want high performance for computation that cares about L1 cache, such as those AI researchers, they will just turn off hyperthreading (or not turn off but the OS guesses well enough to put their 12 processes to 12 separate cores) and then the double L1 caches would be a waste
10:03:21 <wob_jonas> I don't want to say that hyperthreading is always useless, because sometimes people run windows and a browser and have a ton of processes scheduling around each other in wild chaos and the whole thing together is bound on main memory or L3 cache,
10:03:30 <wob_jonas> so in that case hyperthreading can help to reduce context switch overhead,
10:03:54 <int-e> wob_jonas: yeah it would only make sense to me in a isolated container setting (VPS), assuming that /some/ of the hyperthreading benefit survives the effective reduction in cache sizes
10:03:56 <wob_jonas> but for the cases when I actually care for performance, on my computer, not on the boss's laptop when it's running a virus scan, I think hyperthreading is a waste
10:04:51 <int-e> it would mitigate L1 cache based side channels (which probably have a nice name but I don't currently remember)
10:05:01 <wob_jonas> int-e: um, if you have an isolated container, don't you want to not run it on the same core hyperthreaded, because on the same thread timing attacks can cause security bugs? or what kind of isolated containers do you want?
10:05:16 <nakilon> s/AI researchers/casual users of trendy specialised machine learning tools
10:05:22 <wob_jonas> int-e: ok, but is that enough? there's still all sorts of possible timing attacks even if the L1 cache is separate
10:06:02 <int-e> I'm imagining "small" VPSs with 1 virtual core. If you offer hyperthreading then sure, you can give the whole core to the VPS.
10:06:34 <int-e> wob_jonas: I don't know whether it's enough. Probably not... some of the more interesting attacks actually work with the shared branch prediction data.
10:06:35 <wob_jonas> int-e: no, I mean separating the L1 cache isn't enough to isolate the two processes enough for security purposes I think
10:08:30 <int-e> And in the end, the scheduling decisions for individual instructions is so delicately intertwined in hyperthreading... there will be remaining side channels where you can see what kind of stuff the other thread is doing.
10:08:46 <int-e> So yeah, it's probably a losing fight.
10:09:02 <int-e> Up until the point where you have two separate cores ;)
10:09:34 <wob_jonas> but maybe some VPS providers just don't care about the security of their clients?
10:09:44 <int-e> Oh that's for sure.
10:10:26 <int-e> Remember https://www.cloudatcost.com/ ?
10:11:35 <wob_jonas> "virtual crypto miners" wait what?
10:11:48 <int-e> Yeah they found a way to become even more scammy
10:12:08 <wob_jonas> I don't remember because I haven't researched the VPS market much
10:12:11 <int-e> "we're mining crypto but you can help us finance the hardware"
10:12:28 <wob_jonas> so far I don't even have a hosted server (virtual or not) that I pay for
10:13:07 <int-e> I thought you might remember from the old days when HackEgo used to crash once every one to two weeks because the CaC VPS it was on was so great(ly unreliable).
10:13:11 <wob_jonas> I just have a computer at home behind a dynamic IP cable internet that often cuts out, and I'm vaguely wondering if it's even possbile to run a https server behind dynamic IP
10:13:37 <wob_jonas> oh, is that the old hosting provider for the wiki?
10:15:06 <wob_jonas> "virtual crypto miners" is impressive in the sense that it's hard to write a short webpage headline that dodgy.
10:15:43 <wob_jonas> the investment scam ads need more words than that to communicate their scammyness
10:15:48 <int-e> They evolved a bit. The good old $35/lifetime VPS offer is gone. Or was it $70 and permanently 50% off. I forgot :)
10:16:11 <wob_jonas> meh, permanently 50% off is normal, people do that here too
10:16:22 <wob_jonas> even for basically legitimate services
10:17:09 <nakilon> I wonder why I have $ in RASEL
10:17:21 <Taneb> The old RASEL-dazzle
10:17:38 <int-e> 0/- doesn't look like money
10:17:59 <nakilon> I can change / with $ to have lots of money
10:18:14 <nakilon> wob_jonas division by zero gives zero
10:20:45 <nakilon> really, the $ is almost not used actually
10:22:41 <nakilon> only 4 times in brainfuck interpreter
10:23:34 <nakilon> are there any built in or popular unix utility for char stats?
10:24:47 -!- spruit11_ has joined.
10:25:10 <nakilon> https://dpaste.org/QmjQ/slim
10:28:16 -!- spruit11 has quit (Ping timeout: 252 seconds).
10:28:40 <nakilon> (and fungot for comparison https://dpaste.org/ExRY/slim)
10:28:40 <fungot> nakilon: grab the fnord bus. not familiar though. -g is fine as long as people don't delete)
10:29:55 <nakilon> oh and there are english comments in both files (
10:31:00 <nakilon> but still I suppose 1 with g are the most used instructions in fungot and 1 with \ are the most used in my program
10:31:00 <fungot> nakilon: a celebrity of some sort, a human readable spec, but there's an exact address for chead on that " visual_iterate ( chead=0x804c318) at mm_visual.c:13
10:31:53 <ais523> on the subject of hyperthreading, I assumed that it started out as "let's run unrelated programs on alternating CPU cycles to halve the effective pipeline length, helping to hide our long pipelines" (that may be incorrect), but it's turned into "it's wasteful to have a fixed number of instruciton decoders, etc., let's split six decoders between two core-equivalents so that they can do four-and-two or five-and-one, rather than forcing them to have only
10:33:03 <ais523> wob_jonas: I'm trying to work out whether there's any actual distinction between a virtual cryptominer and a subscription service for buying bitcion
10:34:07 <wob_jonas> ais523: I thought it started like "the programmers can't write programs that use the cache efficiently, so the CPU is mostly waiting for memory (or L2 or L3) accesses. if we're memory-bound all the time then we don't need so much of everything else, run two threads together, running whichever thread can proceed because the data from memory arrived"
10:34:55 <ais523> wob_jonas: it could be, sort of, except that the hyperthreads share the L2/L3/memory bottleneck
10:35:14 <ais523> so this is only useful in the rare case that the program is bottlenecked specifically on memory latency rather than memory throughput
10:35:32 <ais523> (this can happen, e.g. with linked lists, but throughput is much more likely to be a bottleneck)
10:35:55 <wob_jonas> so it's more about pipeline than memory, beacuse it doesn't help with memory?
10:37:14 <wob_jonas> ais523: can hyperthreading also be because the programs use too many unncessary context switches, so you may want to run two *related* processes that are communicating and syncrhonizing in one thread?
10:37:28 <wob_jonas> no, probably not, cpus are probably not optimized for the latest stupid fad of bad programmers
10:38:00 <ais523> wob_jonas: when working on this FizzBuzz, I've concluded that algorithms often care a lot about which threads are siblings
10:38:55 <wob_jonas> um ok... but your optimized FizzBuzz is also not what the cpus will be optimized for
10:39:02 <ais523> the FizzBuzz doesn't benefit much from the sibling relationship because it's bound on cache write speed and that's something that's shared between siblings
10:39:08 <ais523> wob_jonas: well, it is, sort-of in reverse
10:39:15 <wob_jonas> it's true that if you have a hyperthreading cpu then the programmer may care on where they bind the threads
10:39:19 <ais523> in that it's being optimized to try to fit the CPUs as accurately as possible
10:39:57 <ais523> if the CPUs had different performance characteristics it might well change the entire algorithm
10:40:27 <wob_jonas> ais523: yes, if you have 12 important threads on a 12*2 hyperthreading cpu then you want to run them on 12 separate cores
10:40:32 <ais523> the funny thing is, I'm not sure you even benefit much from multithreading if you're trying to write the fizzbuzzed output to memory
10:40:55 <ais523> because the bottleneck will be the memory write speed and I think you can go fast enough to saturate that with even one core
10:41:01 <ais523> so the only benefit from a second thread is to run your system calls on it
10:41:11 <wob_jonas> ais523: yeah, unless it's a NUMA machine, because you can do the computation fast enough that it's bound on memory speed
10:41:31 <ais523> oh, good point, NUMA probably means extra memory bandwidth because you can access it from multiple places
10:41:33 <wob_jonas> but if it's a NUMA machine then you'll have two threads, one per NUMA node
10:42:05 <velik> Non-Uniform Memory Access -- computer memory design used in multiprocessing https://en.wikipedia.org/wiki/Non-uniform_memory_access
10:42:07 <wob_jonas> that said, in the odd case of fizzbuzz, you also won't be harmed much by running as many threads as you have cores
10:42:08 <ais523> anyway, the mechanism for reading speed in the original CGCC question doesn't actually require the fizzbuzz to be written to memory, just to a memory address
10:42:31 <ais523> which is a huge distinction, because it lets you keep your fizzbuzz output in cache and just discard it when it gets written to /dev/null
10:42:38 <ais523> so it never touches main memory
10:43:07 <ais523> this means running on as many CPUs as possible to give yourself as much L2 cache as possible to store the output in (I only realised this a few days ago)
10:43:10 <nakilon> I feel like adding references at the bottom of the page, velik you are handy
10:43:22 <wob_jonas> unless by "memory address" they mean a memory-bound IO device, like one that behaves like a really fast serial port that actually throws the data away
10:43:37 <ais523> wob_jonas: nah, it's defined in terms of system calls
10:43:55 <ais523> specifically, requiring it to be possible to read the data from a pipe (but not actually doing the read, it just gets piped to /dev/null)
10:44:25 <ais523> which means that you can vmsplice your own address space into the pipe and not actually copy the generated data at all
10:44:34 <wob_jonas> so you'd fill most of the L1 cache, except that the kernel uses to do the write, then call the write?
10:44:48 <wob_jonas> "copy the generated data" to /dev/null?
10:44:53 <ais523> wob_jonas: right, although I'm currently planning to use the L2 cache for the purpose
10:45:21 <ais523> L1 might be doable, but then the system call overhead gets really large
10:45:40 <wob_jonas> why do you need vmsplice if the speed is measured when the output handle is /dev/null ? doesn't writing to that elide the copy?
10:45:53 <ais523> also, my current algorithm uses most of L1 cache as it is for lookup tables; I could make those smaller but at the cost of using unaligned access
10:45:58 <wob_jonas> I mean I don't know, maybe the kernel doesn't optimize taht and it does copy before discarding
10:46:07 <ais523> wob_jonas: so the command is (./fizzbuzz | pv > /dev/null)
10:46:18 <shachaf> Do unaligned accesses actually matter much these days?
10:46:21 <ais523> pv is like cat with a progress bar
10:46:37 <ais523> but in this configuration, it internally calls splice repeatedly, with stdin and stdout as arguments
10:47:01 <ais523> shachaf: not in normal configurations, but this one is sufficiently abnormal that I think they might
10:47:32 <wob_jonas> shachaf: unaligned access matters if (a) it's across a cache line, or (b) you've optimized your program to an older CPU or at least for potentially running on an older CPU
10:47:33 <ais523> e.g. it wouldn't surprise me if an unaligned 32-byte read that crossed a cache line boundary would require twice the L1 read bandwidth
10:47:52 <ais523> and this doesn't matter in most cases, because most programs aren't bottlenecked on L1 read bandwidth
10:48:09 <ais523> but this one is, it bottlenecks L1 read, L1 write, and L2 write simultaneously
10:48:21 <wob_jonas> shachaf: if you read an unaligned integer within a cache line it's as fast as aligned, but aligning everything is a good heuristic to avoid that
10:48:55 <ais523> the really horrible case is an unaligned access across a *page* boundary; cache line boundaries don't cost much nowadays, but they may be a little slower
10:49:13 <shachaf> Unless it also increases wasted cache space, in which case it might be less clear, I suppose.
10:49:26 <shachaf> Page boundaries are a bad case, sure.
10:49:39 <shachaf> But they're pretty uncommon, especially if you use huge pages.
10:50:06 <wob_jonas> shachaf: also sometimes you *want* unaligned access, even across cache lines, eg. to memcpy with unaligned difference, and for that the guideline is that if you have a choice between unaligned reads and unaligned write, do aligned write and unaligned read
10:50:48 <ais523> wob_jonas: aligned write, unaligned read is usually better, but apparently not always
10:51:04 <wob_jonas> here too the unaligned only matters across cache lines, but reading unaligned is better than reading aligned and then shifting, and is also better than reading aligned and writing unaligned
10:51:14 <wob_jonas> ais523: yes, it's just a guideline
10:51:16 <ais523> I think someone benchmarked all the possibilities (including one where you do both reads and writes aligned and use double vector shifts to adjust)
10:51:45 <nakilon> also the top element can be discarded with '? '
10:52:00 <nakilon> so there are three ways already, what are others?
10:53:12 <wob_jonas> ais523: in bitmap image processing, we often have patterns similar to the Wolfram style cellular automaton, where the output is the same size as the input but depends on three adajcent input pixels. and in that case, aligned reads and shifts may be better.
10:53:22 <wob_jonas> aligned reads and aligned writes and shifts
10:54:12 <wob_jonas> though sometimes the bottleneck is something else and it doesn't matter what you do
10:54:34 <ais523> well, that algorithm would naturally want unaligned reads at the bit level, but there's no way to express those
10:55:00 -!- ais523 has quit (Quit: quit).
10:55:21 <wob_jonas> "the really horrible case is an unaligned access across a *page* boundary" => especially if you want to write a strlen where reading one byte past the nul byte is undefined behavior if it crosses a page boundary
10:55:37 <wob_jonas> and yes, that's a bit different than what you are talking about
10:56:43 <wob_jonas> I would like a malloc-like API that takes four parameters instead of the usual two: size of allocated block, alignment, how many bytes must be readable before it, how many bytes must be readable after it. (you can have two variants of this, one where you know the paramters when you free and one where you don't)
10:56:56 <wob_jonas> usually mallocs only provide two parameters, the size and the alignment
10:57:51 <wob_jonas> unaligned reads at bit level? what algorithm?
11:01:33 <wob_jonas> oh, you're talking about the cellular automaton? well, in the image processing our pixels are large that we don't need that, and even in the Wolfram case you can store the CA such that you don't need finer than byte granularity if you wish, by breaking your space (or large enough pages of it) to eight parts, storing each eighth in a specific bit of
11:01:34 <wob_jonas> the bytes, and putting the eight on top of each other and then manipulating them together. this only works if your neighborhood is small enough, like in Wolfram, not for larger data, but often if the bit level shifts cause a problem (they don't always do) you can avoid them
11:02:27 <wob_jonas> though I'm not too confident in that
11:06:45 <wob_jonas> the Wolfram CA is different in that you want to iterate your operation a lot of times
11:06:57 <wob_jonas> unlike in the pixel bitmap case, where you want much fewer iterations
11:07:09 <wob_jonas> so for the CA you don't want to rearrange the pixels
11:16:01 -!- arseniiv has joined.
12:13:59 -!- dyeplexer has joined.
12:37:36 <esolangs> [[Kolmogorov]] M https://esolangs.org/w/index.php?diff=88043&oldid=88024 * Kaveh Yousefi * (+0) Added a linebreak to simulate a paragraph, removed a superfluous empty line, and amended an occurrence of ascii to its capitalized form.
12:50:20 -!- pikhq has quit.
12:50:36 -!- pikhq has joined.
13:15:01 -!- velik has quit (Remote host closed the connection).
13:15:32 -!- velik has joined.
13:19:54 -!- velik has quit (Remote host closed the connection).
13:20:11 -!- velik has joined.
13:36:19 -!- aarchi has quit.
13:36:35 -!- aarchi has joined.
13:38:50 -!- velik has quit (Remote host closed the connection).
13:39:18 -!- velik has joined.
14:14:18 -!- hanif has quit (Ping timeout: 276 seconds).
14:15:30 -!- Sgeo has joined.
14:24:22 -!- src has joined.
14:33:50 -!- faxlore has quit.
14:34:06 -!- faxlore has joined.
14:41:47 -!- sprock has quit (Ping timeout: 268 seconds).
14:45:03 -!- hanif has joined.
14:45:27 -!- tromp has quit (Quit: My iMac has gone to sleep. ZZZzzz…).
14:50:54 -!- wob_jonas has quit (Quit: Client closed).
15:05:32 -!- tromp has joined.
15:10:36 -!- hanif_ has joined.
15:12:09 -!- hanif has quit (Ping timeout: 276 seconds).
15:22:00 <nakilon> it happens that in factorial example I put on wiki both $ are safely replaceable with -, because in both cases there is 0 on top
16:15:32 -!- sprock has joined.
16:26:30 -!- vyv has joined.
16:30:44 -!- tromp has quit (Quit: My iMac has gone to sleep. ZZZzzz…).
16:37:18 -!- hanif_ has quit (Ping timeout: 276 seconds).
16:49:26 <esolangs> [[RASEL]] https://esolangs.org/w/index.php?diff=88044&oldid=87906 * Nakilon * (-71) spec v2: deprecated '$'
16:51:36 <esolangs> [[Velik]] M https://esolangs.org/w/index.php?diff=88045&oldid=87985 * Nakilon * (+38) note that it runs spec v1
16:54:47 -!- tromp has joined.
16:57:45 <nakilon> '$' has appeared to be in most cases replaceable with just '-' because it is usually used when if you leave the loop and you need to pop the nullified counter that was used there
16:59:54 <Sgeo> I'm confused by matrices again. When a mathematician sees m_12, does that usually refer to row 1 column 2, or row 2 column 1?
17:00:10 <shachaf> Or does it refer to entry 12?!
17:00:37 <shachaf> Presumably the diagram at https://en.wikipedia.org/wiki/Matrix_(mathematics) can help.
17:01:24 <Sgeo> So DOMMatrix does it the other way around, because...? https://drafts.fxtf.org/geometry/#DOMMatrix
17:04:16 -!- hanif_ has joined.
17:09:09 -!- hanif_ has quit (Ping timeout: 276 seconds).
17:09:23 -!- sprock has quit (Ping timeout: 265 seconds).
17:11:35 -!- tromp has quit (Quit: My iMac has gone to sleep. ZZZzzz…).
17:16:17 -!- sprock has joined.
17:26:08 -!- hanif_ has joined.
17:31:25 <nakilon> wow, that DOMMatrix thing is surprising
17:38:30 <Cale> That's a bold move to change convention like that, but tbh, I think column/row makes more sense if we were doing it all over again, and seems especially appropriate if you only have the geometric usage of matrices as linear maps in mind. The ith column of a matrix are the coefficients (in terms of the basis on the codomain) of where it sends the ith basis vector (of the domain).
17:39:13 <Corbin> The convention doesn't matter; what matters is not changing the convention midway through a module.
17:39:16 -!- immibis has joined.
17:39:25 <b_jonas> there are like three or four orthogonal arbitrary convention choices for how matrixes work
17:40:17 <Corbin> Cale: WTB a matrix-maths library which encapsulates matrices without the ability for programmers to witness the internal indexing.
17:40:54 <Cale> Is that just linear?
17:41:30 <b_jonas> one for when you multiply do you match the column index of the first factor with the row index of the second or backwards (most people agree on the former); one for whether your covariant vectors are row vectors or column vectors (this one has much more variance); one for what order you write the two indices; one for whether you represent the matrix row-major or column-major; and one for which factor
17:41:36 <b_jonas> you conjugate when you compute an inner product
17:41:38 <b_jonas> I guess that's five mostly independent choices
17:42:21 <Cale> Some of those are not entirely orthogonal
17:42:24 <Corbin> Cale: Ha, I'd forgotten it exists, thanks: https://hackage.haskell.org/package/linear
17:43:09 <b_jonas> Cale: yeah, you may have to do a basis change on these to get them orthogonal,
17:43:15 <b_jonas> but they are five linear independent choices
17:43:28 <Cale> In the sense that while you can flip some of those conventions relative to each other, you'll also make the notation worse by doing so
17:44:20 <Cale> Like, it's very important that matrix-matrix multiplication corresponds to function composition of linear maps, and matrix-vector multiplication corresponds to function application
17:44:36 <b_jonas> Cale: function composition in which direction?
17:44:46 <Cale> In whatever direction you write function composition
17:44:58 <Cale> Which should match with function application
17:45:04 <b_jonas> the matrix multiplication always correspond to function composition and function application, you just have to write the two factors of the matrix multiplication in the right way
17:45:19 <b_jonas> Cale: yes, but people never agree which way function compositions and applicatio ngo.
17:45:34 <b_jonas> algebraists sometimes put the function on the right, analysis the function on the left
17:45:36 <Cale> For some value of "never" where 99.9% of people agree
17:46:08 <b_jonas> and those same algebraists may put the covariant vectors on the right, so it's backwards from function application
17:46:15 <Cale> (and some are just agreeing more begrudgingly than others)
17:46:27 <b_jonas> some people even write function composition backwards compared to function application
17:46:28 <Cale> If you want the opposite convention, I recommend using exponents
17:46:58 <Cale> i.e. (x^f)^g = x^(fg)
17:47:03 <b_jonas> Cale: the exponents are mostly for non-linear functions though
17:47:14 <b_jonas> inspired by how conjugation is sometimes notated by an exponent
17:47:20 <Cale> Yeah, it happens with group actions, but not so much with linear maps
17:47:36 <b_jonas> and some morphisms behave sort of like conjugations, so much that they call them outer conjugations
17:49:37 <Cale> But like, choosing one direction for composition and the opposite for matrix multiplication would just be bad. Also, choosing to have vector-matrix multiplication be the opposite way around from matrix-matrix multiplication would be really perverse
17:50:10 <Cale> It's possible to be much more confusing than necessary if you pick the combination of conventions badly
17:51:03 <b_jonas> Cale: ok, but I didn't count function composition among the five, so is that a problem?
17:51:19 -!- Koen_ has joined.
17:51:22 <b_jonas> I mostly didn't count it because it doesn't really just concern matrices or vectors, but still
17:51:44 <b_jonas> so wouldn't that be just the one convention about which side of the product the covariant vector goes?
17:52:29 <b_jonas> as in, if you write function applications with the function on the left, then you likely consider column vectors covariant, unless you use the rare backwards matrix multiplication convention
17:53:08 <Cale> So yeah, you can write your vectors as the "wrong" type of matrix for the matrix multiplication rule, which would be needlessly confusing
17:53:42 <Cale> and you could also define vector/matrix multiplication in a way which didn't agree with how you defined matrix/matrix multiplication, in another sense
17:54:13 <b_jonas> Cale: er no, I certainly don't consider defining vector/matrix multiplication the opposite way from matrix/matrix multiplication
17:54:18 <b_jonas> I've never heard of anyone attempting that
17:54:27 <Cale> Yeah, it would be extremely dumb
17:56:07 <b_jonas> but still, there's the choice where you write (covariant) vectors as row vectors and put a matrix on the right of the vector in matrix multiplication, and the convention where you write (covariant) vectors as column vectors and put the matrix on the left side for a matrix multiplication, and both of those are non-rare
18:07:05 -!- dutch has quit (Quit: WeeChat 3.2).
18:13:10 -!- perlbot has quit (Ping timeout: 240 seconds).
18:13:28 -!- simcop2387 has quit (Ping timeout: 252 seconds).
18:13:31 -!- Argorok has quit.
18:13:45 -!- Argorok has joined.
18:21:08 -!- dutch has joined.
18:26:14 -!- dyeplexer has quit (Ping timeout: 265 seconds).
18:33:49 -!- hanif_ has quit (Quit: quit).
19:07:24 -!- oerjan has joined.
19:16:02 -!- sprock has quit (Ping timeout: 260 seconds).
19:40:02 -!- Koen_ has quit (Quit: Leaving...).
19:42:14 -!- delta23 has joined.
19:56:47 -!- perlbot has joined.
19:59:01 -!- simcop2387 has joined.
20:00:45 -!- tromp has joined.
20:09:31 -!- sprock has joined.
20:14:37 -!- tromp has quit (Quit: My iMac has gone to sleep. ZZZzzz…).
20:16:20 -!- riv has quit (Quit: Leaving).
20:17:58 -!- riv has joined.
20:27:37 -!- tromp has joined.
20:38:12 -!- tromp has quit (Quit: My iMac has gone to sleep. ZZZzzz…).
20:48:18 -!- vyv has quit (Quit: Konversation terminated!).
20:51:46 -!- immibis_ has joined.
20:54:37 -!- immibis has quit (Ping timeout: 265 seconds).
20:55:05 -!- sprock has quit (Ping timeout: 268 seconds).
21:00:59 -!- Lord_of_Life_ has joined.
21:01:46 -!- Lord_of_Life has quit (Ping timeout: 252 seconds).
21:03:42 -!- Lord_of_Life_ has changed nick to Lord_of_Life.
21:10:10 -!- tromp has joined.
21:19:42 <esolangs> [[]] M https://esolangs.org/w/index.php?diff=88046&oldid=88018 * Camto * (-2) Well I mean it is, isn't it?
21:21:10 <esolangs> [[Subreal]] M https://esolangs.org/w/index.php?diff=88047&oldid=88027 * Camto * (-2) Now there is an implementation.
21:35:45 -!- sprock has joined.
21:58:04 <esolangs> [[Matrixfuck]] https://esolangs.org/w/index.php?diff=88048&oldid=87501 * Heptor * (-41) /* Notes */
22:07:06 -!- riv has quit (Quit: Leaving).
22:07:31 -!- tromp has quit (Quit: My iMac has gone to sleep. ZZZzzz…).
22:08:52 -!- riv has joined.
22:41:58 -!- hendursa1 has quit (Quit: hendursa1).
22:42:58 -!- hendursaga has joined.
23:11:45 <Corbin> I worry about Discord culture sometimes. I think that more than one contributor over there has missed the idea that esoteric PLT/PLD is not just "lol silly syntax" or "gl writing real programs" but an attempt to enrich mainstream language design by exploring unexamined avenues.
23:14:40 <esolangs> [[Matrixfuck]] https://esolangs.org/w/index.php?diff=88049&oldid=88048 * Heptor * (+74) Add interpreter
23:17:07 <esolangs> [[Matrixfuck]] https://esolangs.org/w/index.php?diff=88050&oldid=88049 * Heptor * (+8) /* Syntax */
23:19:10 -!- arseniiv has quit (Ping timeout: 268 seconds).
23:28:31 <b_jonas> Corbin: a lot of articles on the wiki are like that too
23:29:46 <Corbin> Yes. The wiki seems to be balanced by an unwritten rule that some pages are actively maintained by their authors, and that there should not be a single unified style or presentation. This isn't bad, but it will make the situation more obvious.
23:29:59 <zzo38> Well, esoteric programming can involve many things, although it is not very good if they missed the idea like you say
23:30:17 <b_jonas> I hope you're interpreting "enrich" and "exploring unexamined avenues" in a general enough sense
23:30:25 <b_jonas> or else lots of good esolangs fail it too
23:30:35 -!- oerjan has quit (Quit: Nite).
23:31:10 <zzo38> I don't know about Discord, but I see the wiki. I suppose, like they say, ninety percent is no good (I haven't actually counted, though)
23:32:15 <Corbin> I think that e.g. the Trivial Brainfuck Substitutions are a much better critique of the situation than I could give.
23:34:13 <Corbin> I just wish that it were possible, through wiki nudges alone, to inspire a healthier PLT environment. At least it's not a barren tribalist wasteland where everybody's arguing over which Lisp is best.
23:36:58 -!- j-bot has quit (Ping timeout: 252 seconds).
23:37:12 -!- j-bot has joined.