« first day (2054 days earlier)      last day (2888 days later) » 

sbi
9:01 AM
Given the vector's poor performance for insertion in the middle, it's probably the latter.
 
user1804599
@sehe it's impossible
 
@sbi I'd say append all of them, then sort them in this manner, take the max to its spot in [start,end], end = spot, recur.
 
user1804599
It's the only thing I care about.
 
user1804599
I want to be happy.
 
sbi
@Khaled.K What?
 
9:03 AM
@sbi Depends on the size
And frequency
If you do it a lot for not-tiny vectors then maintaining the order will likely be better
 
sbi
Yeah, I know. However, this is a piece of library code.
 
For small vectors it shouldn't matter either way anyway
 
For small vectors you could just use linear search.
 
sbi
@CatPlusPlus Really? A common map key is std::string. If SSO fails, inserting in the middle is going to be quite expensive. However, if it's std::pair<const int,int>, doing so might be cheap...
@StackedCrooked Yes, I could. But would it be faster than binary search?
 
Insertion in the middle should be able to move
 
sbi
9:06 AM
C++03
 
@sbi Sometimes. (I don't have the definite answer.)
 
sbi
@StackedCrooked Really? When? Why?
 
Ven
Now, implementing nested sets in C++ for our ORM...
 
Anyway insertion in the middle is linear wrt distance to the end, sorting is linear or worse wrt total size
 
Btw, here's experiment I did last weekend It's a map that uses separate arrays for keys and values. The way it needs customize map::reference is ugly though (kinda like vector<bool>).
 
9:11 AM
Really just measure with some test sets
 
@sbi I did some benchmarks in the past. I found that for up to 30 elements linear search was often faster. The results were not very consistent though.
 
sbi
@StackedCrooked Oh. No explanation, though?
 
Binary search is implemented using (mostly unpredictable) branches. While linear search uses mostly predictable branches.
 
nwp
@sbi going through memory linearly is fast, branches are slow
 
sbi
@nwp If you have 30 elements, binary search is not likely to miss the cache.
 
nwp
9:14 AM
in other news, university fucked me over again and forces me to repeat a math class
 
Cache is one thing, branch prediction is another
 
nwp
I wonder how they will fuck me over next
 
sbi
@CatPlusPlus Oh, right. That would be an explanation.
 
@rightfold maybe you should travel the world for a bit. Expand your horizon instead of shrinking it. Honestly, I'm not saying you shouldn't feel bad - that's alright, I can only imagine half - but I'm convinced happiness has a lot to do with letting go. Call me a buddhist
@StackedCrooked I thought you posted about this ~5 weeks ago (? ±3 weeks probably :))
 
@sbi But I really cared about performance I'd optimize it for the common usage patterns by the application.
@sehe I've toyed with several variations.
 
sbi
9:18 AM
@StackedCrooked This is library code. It's going to be used in different contexts.
 
@sbi prefetch favours linear reads
 
user1804599
@sehe Most places are dangerous for people like me but I've always wanted to visit Norway so I guess I'll do that one day
 
Ven
\o/
 
sbi
@sehe We were talking 30 elements.
 
You could also go to a safe place. Spend a few months in a Kibutz (if that's still a thing)
 
9:19 AM
General purpose code seems to be more about avoiding the worst case rather than optimizing for the common cases.
9
 
@sbi So? I'd go with linear search without blinking. I'd be very surprised if you got benefits from anything more complex
 
user1804599
@sehe Lounge<C++>
 
@StackedCrooked why not do branchless binary search?
 
Ven
@sehe don't say that to someone islamophobic like rightfold
 
usually cache misses fuck binary search - if you have 30 elements that shouldn't be a problem though
 
9:20 AM
@orlp I don't know how to do that.
 
sbi
@sehe That 30 elements was @Stacked's tests, not necessarily our use cases.
 
@Ven Because it doesn't really exist. I meant to think out of the box. The box is clearly too small
@sbi Oh, disregard :)
 
sbi
@StackedCrooked That's always a good reason to not to do something.
Mhmm. Come to think of it, most maps I have seen would contain less than 10 items...
 
@StackedCrooked you basically turn the if statement into a cmov or adding to an offset
another thing to consider is moving recently accessed members to the front
 
nwp
@sbi but you would still optimize for thousands of elements right? For 10 items you can use a linked list and it would be just fine.
@orlp how does that help the branch predictor? Instead of not knowing where to go it doesn't know which data to fetch.
 
9:23 AM
@nwp there are no branches left then
not sure why the branch predictor is relevant
do you mean the cache preloader?
 
nwp
probably
more like CPU in general
 
4 mins ago, by orlp
usually cache misses fuck binary search - if you have 30 elements that shouldn't be a problem though
with 30 elements there is no cache misses to speak of
 
nwp
I don't see how replacing ifs with offsets improves speed
 
it should fit in 1-2 cache lines
 
nwp
hmm maybe, CPU architectures are weird
 
9:26 AM
@orlp that's a good one
 
@StackedCrooked the trick I usually do
is when an element at index i is accessed, is swap it with the element at i/2
@StackedCrooked this is a branchless binary search
int* branchless_bsearch(int x, int arr[32]) {
    int* p = arr;
    p += (p[16] <= x) << 4;
    p += (p[ 8] <= x) << 3;
    p += (p[ 4] <= x) << 2;
    p += (p[ 2] <= x) << 1;
    p += (p[ 1] <= x) << 0;
    return p;
}
 
nwp
@orlp still looks like you flush the pipeline 50% of the time and gain no speed
is it actually faster?
 
@nwp how would you flush the pipeline?
as I said before, there are no branches here
comparison is not a branch
branchless_bsearch(int, int*):              # @branchless_bsearch(int, int*)
        cmpl    %edi, 64(%rsi)
        setle   %al
        movzbl  %al, %eax
        shlq    $6, %rax
        leaq    (%rsi,%rax), %rcx
        cmpl    %edi, 32(%rsi,%rax)
        setle   %al
        movzbl  %al, %eax
        shlq    $5, %rax
        leaq    (%rcx,%rax), %rdx
        cmpl    %edi, 16(%rax,%rcx)
        setle   %al
        movzbl  %al, %eax
        shlq    $4, %rax
        leaq    (%rdx,%rax), %rcx
        cmpl    %edi, 8(%rax,%rdx)
 
@orlp Oh, I see how it works now.
 
user1804599
what is kibutz
 
nwp
9:34 AM
@orlp every time you dereference p you have to guess where that memory is and put it on the pipeline without knowing p. If you guess wrong you need to flush the pipeline.
 
user1804599
> A kibbutz (Hebrew: קִבּוּץ / קיבוץ, lit. "gathering, clustering"; plural kibbutzim) is a collective community in Israel that was traditionally based on agriculture.
 
@nwp we're talking 32 elements here
that easily all fits in the cache
 
user1804599
if that includes botany I'll do it
 
nwp
cache != pipeline
 
I'm pretty sure any decent pipeline can detect this situation.
Especially since p sits in a register.
 
9:35 AM
@sbi what is the type of the container.. vector, list ?
 
Ven
@rightfold it includes buttany
 
user1804599
botany suck
 
user1804599
too many bees and wasps
 
user1804599
I hate plants
 
@nwp either way, it's pointless to guess
it might be slower, it might be faster
just profiling can give you an actual answer
 
Ven
9:37 AM
might be both
 
nwp
or neither
 
@nwp besides, what you're describing would be a stall, not a pipeline flush IIRC
there was no wrong execution, unless I'm missing some gross misunderstanding about how out-of-order CPUs work, which we never handled on the uni
@StackedCrooked yeah, it's pretty nifty
I don't know how to make it work (if possible at all) for non-power of two sized arrays
but if you're designing a data structure that shouldn't really be a problem (although I'm aware of the 'can never re-use old memory' problem that the power-of-two growth strategy has)
but I don't really believe that's a problem with current machines, allocators and programming practices anymore
 
@rightfold botany suck best suck
@rightfold face palm best plant
 
Robert Plant good plant
 
9:49 AM
@Khaled.K shuffle a linked list coliru.stacked-crooked.com/a/10a8ab71eee44c39
I often end up making 'dummy elements' to make algorithms with linked lists... uniform
 
You can by fly net in Uluru, you can use it to cover your head
 
Ven
nested sets are awesome
 
I got one
 
@orlp nice but impractical.. should be a loop
 
@Khaled.K what?
what should be a loop?
 
9:54 AM
recursive functions that recur on each item in the list
 
@Khaled.K that's not what my function does?
 
okay I just read your function, it seems that it shuffle through randomly assigning each item to one of two lists, then recur the same process on both of them.
so.. when does it terminate exactly?
 
@Khaled.K theoretically it could go on forever, but expected runtime is n log n
it's very similar to quicksort
 
Associate a random index to each element and sort.
 
@Morwenn is incredibly biased
and requires O(n) memory
 
10:01 AM
@orlp your base case will have a very small chance to stop one of the recurrence branches, other branches will keep recurring forever..
 
Hey, I could create a shuffle_adapter that turns any sorter into a shuffler :D
Totally useless though.
 
@Morwenn sorry
I was a bit confused; your method is unbiased, but still O(n) memory
and it gets biased if you generate duplicate numbers
what is biased is sorting with a random comparison function
@Khaled.K no?
 
Oh, so that's what you meant by « biased ».
 
@orlp oh, I see.. you're doing merge shuffle
 
you should see the algorithm as randomly distributing among two lists, recursing on those two lists, then concatenating them
theoretically you might get unlucky and put 99% of the elements in one list, and 1% in the other
 
user1804599
10:04 AM
@Ven sets are awesome, nested sets are sets, therefore nested sets are awesome
 
but most of the time you get a near 50/50 split, giving expected runtime of n log n
 
Ven
@rightfold well observed
 
you stop when you have a list of one item, which is guaranteed even though the tree being balanced depends on the randomness of the coin flips
 
What is this? (mildly NSFW) youtube.com/watch?v=aC55F8Zm3WI
 
@Khaled.K well, it could still theoretically run forever
 
10:06 AM
I found it accidentally and it is hilarious.
 
if you get a sequence of tails or heads forever out of your coinflips
but that's so unlikely it doesn't matter
@wilx archer
pretty good series
 
@orlp it depends the random number generator distribution
 
@Khaled.K no? I already assumed that coinflip is a fair coin
 
@orlp is the random number generator part of the algorithm?
 
@orlp Congratulations! You have won the duty to remind me to watch this when I get back home from work.
 
10:08 AM
@Khaled.K no, it assumes you provide it with a fair coin through the API coinflip() returning 0 or 1
a fair coin has to be able to produce arbitrarily long sequences of zeroes or ones, otherwise it's not a fair coin
@Khaled.K I'm not aware of an algorithm that can match or beat the expected O(n log n) this algorithm has while maintaining O(log n) memory usage
(for linked lists that is)
 
you mean singly linked lists
 
I believe the same claim holds for doubly linked lists
 
maybe you could check after the split, if one of the two lists is empty, remove an element into it
this should work like aging, against a possible unfairness of the provided coinflip
 
@Khaled.K no
this destroys the unbiased nature of the algorithm
 
if coinflip is fair all the time, that code won't execute
 
10:20 AM
@Khaled.K that's not true
12 mins ago, by orlp
a fair coin has to be able to produce arbitrarily long sequences of zeroes or ones, otherwise it's not a fair coin
 
getting 1000 times tails in a row is unlikely, but if it's impossible with your coin your coin is biased
@Khaled.K keep in mind that an important aspect of a fair coin is that every coinflip is independent of others
the coin doesn't care that it landed on tails 999 times before, it's still a 50/50 for the next flip
 
user1804599
cool it's allowed to prohibit visible religious signs on the work place in the EU
 
user1804599
political ones too
 
nwp
> I forbid you to drink coke because Coca Cola represents an imperialistic political view
 
10:25 AM
@orlp the coinflip is 50/50 all the time, I feel it should be uniformal over the number of items in the list it split
 
@Khaled.K could you rephrase that?
 
nwp
@orlp I think he means the coin should be biased in favor of getting log(n) runtime behavior
 
@nwp but then the algorithm is broken
at that point you don't have a shuffle algorithm anymore
 
@orlp splitting N items, over N coin flips, in total get N/2 tails and N/2 heads
 
@Khaled.K let me ask you, is this sequence random? 10101010101010101010....
 
10:29 AM
@orlp you can use random numbers directly, or choose from a list of items randomly
 
I don't know what you mean by that
 
N = 4, R = [0 0 1 1], for 1 to N: remove a random item from R, split current into it, current = current->next
 
nwp
@Khaled.K you kind of reduced the random shuffle problem of a list of objects to a random shuffle problem of a list of bits
 
@Khaled.K that is O(n) memory
you need n bits to store R
by the way, it's impossible to get an algorithm that shuffles a list fairly in guaranteed finite time for any input just by using random coinflips
a shuffle algorithm must return one of the n! possible permutations with equal probability
but a random coinflip can only produce 2^n possibilities with equal probability in finite time
and for any n >= 3, n! is coprime with 2^n
 
nwp
@orlp doesn't make sense. The n in n! and the n in 2^n are not the same n. You can totally throw the coin more times than you have elements in the list.
 
10:42 AM
@nwp correct, but they are still coprime
meaning one will never be a multiple of another
 
@VermillionAzure Emacs, of course!
 
@nwp as an example, try to create an algorithm that fairly picks 0, 1 or 2 using just coinflips
you can only do it by potentially running forever (by rejecting bias)
 
@StackedCrooked Astute observation.
(I just wanted to use the word astute.)
 
@StackedCrooked pdqsort tries to do both :)
 
@orlp what if coinflip returns 0, 1 or 2.. and when it's 2, you split the next two items fairly
 
10:49 AM
@Khaled.K you have a three-sided coin?
or am I misunderstanding you?
 
Ven
Every coin is three-sided...
8
 
@Ven :P not our mathematically perfect coin
just like our spherical cow in a vacuum
 
that emits milk evenly in all directions?
 
if coinflip return 0, 1, 2 with P = 1/3, if 0: split item into A, 1: split into B, 2: split into A then B
 
@Khaled.K a coinflip only returns 0 or 1
 
user1804599
10:54 AM
coinflip is the dual of inflip
 
not in a ternary universe ;_;
 
int coinflip(){ try{ return coin.flip(); }catch(...){ return 2; } }
 
user1804599
EU in a nutshell
 
user1804599
11:11 AM
23 days until its collapse
 
Ven
lol.
shut up wrongfold
 
user1804599
can i be brexcited
 
Ven
you can be breast-excited
 
user1804599
> When may a policeman draw his service sword?
> Ripping open larynx can work de-escalatingly
 
Ven
In that it's hard to do worse later
 
11:20 AM
As of may 25 it's more likely that they don't leave EU
sorry exitfold
 
user1804599
RIP freedom
 
user1804599
I heard many eligible students aren't gonna vote because they have exams and music festivals on that day
 
Them (or anybody for that matter) leaving the EU would be a very bad thing for p much anybody
 
user1804599
No, it'd mean a further breakdown of this harmful bureaucratic self-enriching imperialist bulwark.
 
US would be pissed at them for leaving and is promising bad exchange rates, it would p much mean the end of the EU in the long run and in general would make the entire europe weaker and possibly on the verge of war (even though that's less likely nowadays).
In a period of time where stability in europe is more important than ever.
 
user1804599
11:26 AM
Stability requires democracy, and democracy is not on the EU's agenda.
 
How is it not democratic?
 
@rightfold "Stability requires democracy" playing devil's advocate, <citation needed>
 
Actually stability was often achieved with almost no democracy, but whatever
> To become a member, a country must meet the Copenhagen criteria, defined at the 1993 meeting of the European Council in Copenhagen. These require a stable democracy that respects human rights and the rule of law; a functioning market economy; and the acceptance of the obligations of membership, including EU law.
> The treaties declare that the EU itself is "founded on the values of respect for human dignity, freedom, democracy, equality, the rule of law and respect for human rights, including the rights of persons belonging to minorities ... in a society in which pluralism, non-discrimination, tolerance, justice, solidarity and equality between women and men prevail."
I'm guessing at this point you are just trolling so I'm slowly going to walk out of this discussion.
 
user1804599
Insofar I do believe that even if a majority votes leave, they'll try to find some way out to kind of make it a yes anyway
 
user1804599
like they did with the european constitution referendums
 
11:30 AM
Thankfully
 
user1804599
but that will again show the undemocratic nature of this sick bulwark
 
user1804599
and enrage the people once more
 
The people are unable to make such a decision because they lack the knowledge of what it means to be in the EU
 
user1804599
so a leave vote majority is a win either way
 
There shouldn't even be a referendum in the first place
 
user1804599
11:37 AM
There should be a referendum about important topics like these periodically.
 
user1804599
Binding, that is.
 
user1804599
Referendums are great. #PeopleForPresident
 
@Shoe Ah, so you are against democracy.
The smart choice.
 
user1804599
@sehe I got some answers to my Vim Q
 
user1804599
11:44 AM
0
Q: How do I configure Vim to not indent the current line upon hitting return?

rightfoldI have the following text: "); When I hit return in insert mode, Vim creates a new line (as expected), but also indents the line on which return was hit: "); Vim only does this with some lines, presumably when it thinks the indentation is incorrect. How do I configure V...

 
user1804599
@Ven No time for C++
 
I think it's unprofessional to compare programming languages directly
 
@Khaled.K lol, what?
 
yeah you need to declare pointers to them first
 
Ven
ew depending on memory layout.
 
user1804599
11:50 AM
Rust > C++
 
user1804599
I think that's a pretty fair comparison.
 
@Griwes Democracy doesn't mean referendum all around FYI
 
@Shoe No - democracy just means that idiots that lack any kind of knowledge make decisions :P
 
user1804599
yay
 
user1804599
the answer works
 
user1804599
11:57 AM
clearing indentkeys removes the bad behavior
 
@Griwes How is that different from say monarchy? ISTR that not all of them were particularly bright :P
 
user1804599
<fieldset> is underrated.
 
Did I say anything from monarchy? :P
At least in monarchy it's clearly known who's the idiot.
 
Ven
@rightfold fieldset+legend = <3
 
user1804599
12:10 PM
the legendary fieldset
 
Ven
@orlp cock cock cock cock
 
@Ven no, coke
 
Ven
coooock
 
user1804599
did somebody mentionc ock
 
Ven
12:13 PM
Ook.
 
@Griwes My point was, it's not democracy specific :P
 
user1804599
I get hungry when people mention cock
4
 
user1804599
pun not intended
 
@rightfold I believe the girl in the video was thirsty
 
12:24 PM
@fredoverflow /cc @R.MartinhoFernandes
 
23 hours ago, by Ramy
Someone know if exist a integer with this value? 0xe73ac1da
wat
 
user1804599
"Ownership" is such an inconsiderate word :S like owning slaves :S how could Rust use this term :(
 
What else would you propose?
 
user1804599
@fredoverflow dat frame rate
 
hence the screenshot
 
user1804599
12:26 PM
@fredoverflow "responsibility of resource releasing"
 
user1804599
RRR is the pirate form of RAII
 
user1804599
In Rust you can do funny stuff like this:
 
user1804599
fn f() -> int {
    g(return 1)
}
 
user1804599
f will always return 1 and it'll never call g
 
Ven
12:29 PM
good
 
wat, return as an expression?
 
user1804599
return expressions never return!
 
that.. is wtf.
that's even worse than throw throw throw throw throw throw throw 1;
 
 
user1804599
@Puppy no, it is very nice
 
user1804599
12:34 PM
Statements suck.
 
user1804599
Can't put them anywhere you want.
 
user1804599
-1
 
they don't make sense anywhere you want
 
Ven
obviously you're supposed to throw return 1;
they do!
 
your example is an excellent motivator as for why that's true
 
Ven
12:36 PM
g(has_value() && value_is_correct() ? value : throw "bad value");
 
user1804599
Coooool
 
user1804599
The last field in a Rust struct can be of an unsized type
 
user1804599
I didn't know that!
 
user1804599
like flexible arrays in C
 
user1804599
@BartekBanachewicz I'm gonna implement multithreaded Lua in Rust.
 
user5058091
12:48 PM
Hi
 
@wilx it just seem to me just like comparing a knife to a hammer in how good it cut, ignoring the fact that the hammer was not built to cut in the first place.
 
@Khaled.K Bad analogy.
 

« first day (2054 days earlier)      last day (2888 days later) »