« first day (1918 days earlier)      last day (3256 days later) » 

19:00
@JerryCoffin I suppose so.
@MadameElyse the problem with map is that I can't find the n-th element
I heard cuckoo hashing. Seemed like a fun concept.
yes, its bad
user1804599
@StackedCrooked Two days ago I reduced a function's execution time from 4s to .5s by moving hash table lookups out of a loop.
But with RB-tree it can be done easy
want container like map, but a[i] mean i-th element in a
with cheap insertion and deletion
19:03
@SashaMN std::map<size_t, whatever> (and insert with increasing keys).
@JerryCoffin no, it will not work
Binary search was explained to me as looking up a word in the dictionary: start in the middle and gradually get near the right page halving the number of pages each time. But now I start to think it's more like hash lookup. We open the book at a place near the right word and then resort to linear search.
For example I have {1, 2, 3, 5}
and want insert 4
what should I do?
it's not possible to solve this problem using STL containers only
@SashaMN give up
But possible with RB-tree
user1804599
19:05
@SashaMN find a single spot that is directly next to both an element greater than 4 and an element smaller than 4.
@SashaMN we all want that
user1804599
Pretending negative infinity is at the front and positive infinity is at the end.
@StackedCrooked Not quite. The original explanation is correct. The problem is that looking a word up in the dictionary is more like a hash lookup than a binary search, so the analogy is just not good, even though the underlying explanation is correct.
unless the word starts in the interval a b c d e f or x y z
19:06
well to be fair a person looking up a word in a dictionary is more like a trie than a hash table, but close enough.
user1804599
@Puppy that's what he said lrn2read
I open the dict in the middle
because I only know where letters go if I enumerate the alphabet :D
user1804599
You are bad at "it" disambiguation.
@Puppy But an experienced user can open the book at the right page 9/10 times. So he's evolved from binary searcher to hash lookup master.
@StackedCrooked A trie is more correct.
user1804599
19:09
A power user upgrades from physical to digital dictionary.
The index trail thingy?
each region of the dictionary is reserved for buckets a, b, c, etc, and then you just index into the dictionary to the correct bucket.
then recursively repeat the process until the desired word is found.
human users only go to linear search at the end because the dictionary is of known finite size and the buckets aren't that large
user1804599
aaa dammit
@SashaMN Presumably you want the 4 at the end, not between the 3 and the 5? If so, go back, read what I just said, and use it.
user1804599
you know
user1804599
19:10
there could be a major global magnetical catastrophe and all work we've done in our lives would be gone
@JerryCoffin ofc between 3 and 5
Letters are also not evenly distributed. This is bad news for the hash guy.
user406009
@StackedCrooked Probably more like an interpolation search than a binary one.
goddamnit
user1804599
@StackedCrooked Exercise: devise an optimal hash function for English words.
19:11
@StackedCrooked No, what we use is (sort of) an interpolating search--which can also be used on computers, and assuming reasonably predictable distribution, normally has complexity something like O(log log n).
user1804599
You have two hours.
I've broken codepuppy locally but can't figure out why
Git says the file was not changed
user1804599
@Puppy Must be a hash collision.
@SashaMN In that case you apparent just want a set (or multiset, if you want to allow duplicates).
user406009
Interpolation search is extremely interesting.
19:12
TIL log log n is a thing
user406009
@StackedCrooked The basic idea is that you can use the distribution of your source data to speed up your search.
user1804599
@StackedCrooked Is that when your key is a binary tree?
user406009
You can apply similar techniques even if the distribution is non-uniform.
Just for clarification: current state of container: {5, 6, 7, 10}.
I want to get 4-th element: 10
I want to add element 8: {5, 6, 7, 8, 10}
I want to get 4-th element again: 8
@Puppy Maybe it's not longer binary.
19:14
hmm
user1804599
Writing parsers in Perl 6 is really fun, because it's a language feature: doc.perl6.org/language/grammars
@StackedCrooked aka "pseudo-constant". Technically, it does grow, but so slowly it almost never matters in reality.
Emscripten isn't properly handling having more Emscripten'd JS files added.
user406009
In computer science, an order statistic tree is a variant of the binary search tree (or more generally, a B-tree) that supports two additional operations beyond insertion, lookup and deletion: Select(i) — find the i'th smallest element stored in the tree Rank(x) – find the rank of element x in the tree, i.e. its index in the sorted list of elements of the tree Both operations can be performed in O(log n) time in the average case; when a self-balancing tree is used as the base data structure, this bound also applies in the worst case. To turn a regular search tree into an order statistic tree, the...
Yeah. Log2 is already so damn hard to grow.
I keep adding zeros and it only grows by 10 or so.
Which is good of course.
19:15
@Lalaland I know about it. But its not STL container)
Unless you are bored and want a duel with log n.
user406009
@SashaMN There is no STL container for your specific needs.
user406009
Closest is maybe priority_queue.
@Lalaland I know this too)
But @JerryCoffin is trying to suggest me something
@SashaMN I was, but I didn't understand your intent at the time.
19:23
@SashaMN Thread carefully. Several people here are starting to suspect you are an idiot.
Either that or we are missing something.
I made a logo for my haskell C64 emulator
*std::next(set.begin(), 4)
you can tell it's very original
Oh. I get it now.
top quality
can the haskell guys sue me if I use their logo like that on a school project
19:25
@SashaMN Isn't that how std::vector::erase/insertion works?
@AlexM. french haskell :D
@Mr.kbok lol now that you mention it
@StackedCrooked in O(N) time?
Oh, wait vector is unordered.
19:25
@StackedCrooked good morning
@SashaMN boost::container::flat_set<T> is what you want probably. (It's log n for lookup. Not sure for insertion.)
or a normal std::set
facepalm
@milleniumbug I assume he was talking about how to do it with sequential storage.
@AlexM. need more commodorification imo
19:27
@Mr.kbok that means effort and knowing how to use gimp
@SashaMN well, it's your fault for not specifying your problem correctly
I can't use gimp
@AlexM. Don't, and use a vector graphics editor instead :D
@Mr.kbok it looks a bit better like this, I'll leave it like that for the moment dl.dropboxusercontent.com/u/17635452/logo.png
@milleniumbug He gave a SSCE using 12 digits.
19:28
use illustrator or inkscape
@milleniumbug its not my problem, i know the answer.
I just wrote that it is not possible using stl containers only.
@SashaMN Insertion is O(N). (Adding an element to the beginning will require moving all elements one spot to the right.'
@StackedCrooked I want faster container for this
@SashaMN Ok. If all else fails use std::list. It's unbeatable in many areas.
19:31
@StackedCrooked with random access?
RB tree with some improvements give:
O(logN) for insertion/deletion, nth_element, find.
@SashaMN It's legendary for it's random access performance!
user406009
@StackedCrooked Legendarily bad that is.
Ok.
Skip lists seem like they could help. Never used those though.
@StackedCrooked yes, its possible with skip lists
19:36
@SashaMN If you want a serious answer you should try cs.stackexchange or something.
@StackedCrooked I know the answer :)
@SashaMN is it a heap?
@StackedCrooked no, SuperMegaUltraFast container
Ah.
Maybe your container can exist if the user is traveling at the speed of light.
if you're travelling at the speed of light, do you still experience time?
in that case, maybe every operation is O(0)
19:44
Big-O zero. It almost sounds like an unspoken taboo.
O(1) is best thing you can get legally. The real deal is O(0) though.
nah
I like my operations to be O(NaN)
O(NaN) The Destroyer
user406009
O(1/n) is the best complexity.
user406009
Gets faster when the data is larger.
O(1/n^n)
user406009
19:47
IIRC, there is actually a search algorithm with that sort of complexity.
user406009
@Lalaland O(1/n) for example the probability of rehash)
user406009
O(n/m)
for each insertion
in hashtable
@Lalaland The Singularity :p
19:50
the wii u sure is expensive O_o
you can get xbawks and ps for cheaper
I'm in my house every weekend. I feel happy there's a song that shares my feelings.
Watching youtube rocks.
I was assigned this week to monitor a performance issue.
Thing is the code is so bad that I don't know how to explain it.
The person who wrote the code is a senior and has this attitude of being superior.
The objective is counting packets coming in on the network card.
His mountain of code has them travel three concurrent queues before they reach that stage.
The processor finally received "ReceivedNetwork" objects. Getting the timestamp requires two virtual methods and multiplication by 10.
@StackedCrooked Ensuring your position through obfuscation
Also it leads to memory from the nic processor. Causing the cacheline owership to change.
Getting the packet size requires an extra header.
The object has a size method. But you need to subtract the ethernet fcs size and he requires us to include another header for that.
This stupid code is now duplicated all over the place.
He invented his own circular buffer
It throws an exception if you try to write when it's full.
It's supposed to be single-producer-single-consumer threaded. And he insisted on using volatile for this for years.
When my boss finally told him to stop than and use proper atomic the code became slower and he used it as a way to prove he was right all the time.
i thought volatile was not threadsafe "enough" if that makes sense
The compiler is free to reorder non-volatile writes accross volatile writes.
So: buf[volatile_index] = x; volatile_index++; can be reorderd
This can cause the consumer to start consuming before the data is actually written.
This can be fixed by adding barriers. But once you add the barriers the volatile is no longer needed. So in the end the volatile never made sense .
20:03
that's not true.
volatile is not threadsafe at all, ever. It's not "not threadsafe enough". It's just not threading-related at all.
and volatile_index is a volatile read there which cannot be re-ordered relative to that volatile write later.
@StackedCrooked also this can't be reordered
My sample code is probably wrong too.
Recently he dominated a meeting demanding that a vector<map> had to be changed to map<vector>. He knows from experience that vector is a bad thing.
@Puppy Well this answer says volatile does part of the things you would need for threadsafety but not all of them. So its not enough to ensure thread safety. Thats what I meant by "not enough", it does some of the things ya want but these dont guarantee thread safety, you need more.
He "proved" that "resize()" actually involves secret overhead because it doesn't compile if the element type is noncopyable.
@StackedCrooked wut
compile time overhead?
(I assume he didn't consider the possibility that resize to a larger size will trigger reallocation and copy.)
No he believes elements are being copied on every resize.
O.o how little of C++ does he know?
His code is super slow. But he used to write much slower code. So he
is experienced now.
Each comment starts with // ---
He litters the code with ifdefs.
20:10
All my comments start with // ;)
One ifdef about a difference in the lowest layer (hardware access) managed to even cross the rpc boundary!
@Borgleader never multiline comments?
@ScarletAmaranth I try not to use those.
user1804599
TOP
> rf
|  script
|  |  command
|  |  |  command:sym<program>
|  |  |  |  expression
|  |  |  |  |  primary-expression
|  |  |  |  |  |  primary-expression:sym<string>
|  |  |  |  |  |  |  identifier
|  |  |  |  |  |  |  * FAIL
>
He believes proper network programming involves putting ifdefs for bigendian/littleendian all over the place.
user1804599
20:11
parser debugger!
@StackedCrooked oh ffs
@AlexM. You know about Full Clip right?
Even though we don't have bigendian systems and never will. So all his bigendian branches are dead code.
@JohanLarsson no
@StackedCrooked topkek
20:12
@AlexM. here
Meanwhile Rob Pike and Kernighan wrote that ifdef for endianness is never needed. These guys designed unix. If anyone had an excuse to use it it would have been them.
@StackedCrooked Relevant
@набиячлэвэлиь His "documentation" always sound like very scary warnings that something "MUST" be some way because it's "correct". He emphasizes the word "correct" a lot. (Remember his volatile usage.)
user406009
@StackedCrooked Dead code is usually broken code IMHE
20:15
and the comments markup tags in them even though it's internal code
lolwat
@JohanLarsson sounds good
@Lalaland Even if hypothetically, his BIG_ENDIAN branches actually worked and were genuinely necessary, a bunch of them are going to be for code that won't exist by the time a big endian machine comes around.
20:31
He used to be proud of his circular buffer class.
user1804599
Now I have to decide whether I want to interpret directly from the AST or compile to bytecode first.
/s
I don't understand how one can code like this. I need to remove all clutter or I'm not able to concentrate.
wait
I thought you said this was concurrent?
Last week wrote a quick spsc_queue out of boredom. It's probably buggy, but at least it 's somewhat structured..
@Puppy Yeah. He calls it lockless programming.
I suppose he's technically correct on that one.
this is tremendously unsafe in every respect.
20:37
Btw, his _begin and _end member variables are not padded.
And value type is T*.
CircularBuffer::Push method starts with: if (!this->IsFull()) {...
I'm not an expert, but I don't think that's lock-free programming works.
this is hideously unsafe.
the whole idea of IsFull can never work in a concurrent way.
Excactly.
@TonyTheLion You said you were interested in ЧO₂ when it works.
At this point I think it would be safe to say the guy is totally clueless.
But he's a senior developer.
And the other programmers are not good enough to understand his code is wrong.
20:42
Standard everywhere no?
But over the years I've been able to show by example that code can be clean, fast and safe.
And now they finally start to believe that this pile of crap they didn't understand is actually not very good code.
Anecdote:
I tell him that volatile is not safe for concurrency because the compiler can reorder around them..
@StackedCrooked You should use python then)
He answers: We compile with -O2 and GCC only reorders when -O3 is enabled. So this code is fine.
@StackedCrooked or maybe Java
but not C++
That is simply plain wrong. I'm seriously gonna tell my boss on the next performance interview that I am unable to respect him as a fellow programmer and that it's impossible for me to take him seriously when he starts taking the word during meetings.
user406009
20:46
@StackedCrooked Perhaps he should be promoted to somewhere he can't do any harm?
Last time he needed to implement a network throttling algorithm that operated at the link-layer.
It was buggy. And he blamed it was caused by my TCP code.
How can TCP break Layer2 throttling?
I mean like. WTF
nice rant
@Lalaland I really hope so.
So this week I was assigned to figure out how to improve the network processing code. And all the code he worked on for multiple years is just a pile of crap.
How do I communicate that?
Usually I managed to find some low-hanging fruit to improve performance and get rid of the job.
> The past several years have seen the development of an exciting new concept
in electrical design. Conventional system design is rapidly being revolution-
ized by the large-scale, single-chip programmable microprocessor.
@StackedCrooked You should link to all of those people broken by signed integer overflow optimizations. Relying on a compiler implementation detail for correct code...
20:49
Sometimes you need good imagination to understand somebody's code.
the hardest part about old docs is trying to remember that they were written 30 years ago
and especially if you need high performance but then don't enable all optimizations? that's stupid
@StackedCrooked Like Puppy - drugs would?
user406009
@Puppy To be fair, it's extremely easy to trigger signed integer overflow in C++.
user406009
I wouldn't be surprised if every program had a couple of overflow bugs.
20:52
@Lalaland We're talking about people who explicitly overflowed and then checked for overflow as a means of detecting overflow.
@Puppy The next day during morning scrum I presented my report of a little research. The fact that CPU's can do out-of-order execution and that changes can become visible to other threads out of order was how I enabled to make him stop defending the reordering thing.
There's been many situations like this. Finally I'm starting to see cracks in his facade of confidence.
user406009
@StackedCrooked It would be hilarious if you can prove that his code is incorrect. Add a couple of explicit thread yields in his code in the right places and watch it blow up.
I have an example when integer overflow is not an error.
for example, when you need to find last 32 bits of the number after the multiplication)
IOINAE
@SashaMN It is an error.
signed integer overflow in C and C++ is undefined behaviour.
20:56
@Lalaland Every time I prove him to be obviously wrong he starts speaking rapidly and loudly and trying to explain something to me that I he thinks don't know in order to restore superiority.
the compiler doesn't give a fuck if in your source program you tolerate, expect or even want signed overflow.
I'm tired of it.
user1804599
set greeting hello;
echo $greeting $env:USER;
user1804599
This program works! Yay!
user406009
@StackedCrooked "Here is a couple of unit tests for your code. Note that it fails unit tests 1, 2, and 3. Would it be possible for you to fix the bug?"
20:59
At one point he had a printout of Alexandrescu's "volatile: The Multithreaded Programmer's Best Friend" on his desk. He mailed the team about it.
I replied that the post described a clever technique to use volatile methods for concurrency.

« first day (1918 days earlier)      last day (3256 days later) »