« first day (749 days earlier)      last day (4191 days later) » 

@StackedCrooked, thanks, that is exactly the worry and point I wanted to explore. I just started to read the standard on the time complexity of move construction.
 
Hmm, not the best test result output pastebin.com/W3da2vbh
 
Xeo
"madness", lol.
 
@R.MartinhoFernandes What the hell...
 
7:06 PM
There's no end to the madness.
 
37 mins ago, by R. Martinho Fernandes
> Consider the extreme case of a string containing a digit 2 followed by 10,000 umlauts followed by one dot-below, then a digit 3. As part of normalization, the dot-below at the end must be reordered to immediately after the digit 2, which means that 10,003 characters need to be considered before the result can be output.
 
Xeo
o_o
 
I could have tested with just 10 umlauts, but...
 
.... What
 
7:08 PM
lol
 
What in the world. Why... why do you have to torture yourself like this?
 
I'm torturing my machine, not me.
 
You're a robot
afaik robot is a type of machine
:P
 
Mwahahaha, passes now.
@ThePhD It's a stress test.
 
@CatPlusPlus wheee it works
 
7:12 PM
And this, kids, is why I need iterators with vectors in them :(
 
Xeo
:/
 
I'm going to switch to SBO soon, though.
 
SBO?
 
Small buffer optimization.
> A Unicode string is said to be in Stream-Safe Text Format if it would not contain any sequences of non-starters longer than 30 characters in length when normalized to NFKD.
lol, 30 characters.
 
Xeo
I don't think you want 30 byte SBO, right?
 
7:14 PM
No. I'm going to make it 4 char32_t, probably.
 
I'd spring for 16, personally.
 
16 bytes?
16 characters is silly.
 
no, it's one cache line.
no point in offering less than one cache line, IMO.
 
99% of codepoints decompose to sequences that are less than four codepoints.
 
oh, right.
 
7:15 PM
@DeadMG There's more stuff in the iterator.
 
I thought you were talking SSO in general
 
@R.MartinhoFernandes Yeah, I was going to account for that in a revision.
 
@DeadMG Ah, no. I'm going to roll my own specifically for this case.
 
hmm
 
7:18 PM
So you get efficiency for normal text, and well... vectors for Zalgo.
 
normalization, comparison/collation, encoding conversion, and a fairly simple container.
then add formatting routines
need I add more?
 
some fun stuff please
 
like?
 
hm..
On second thought the list looks not all that unpleasant.
 
boundary analysis, I added too
I figure that should do
 
I could write you a program that uses it all.
It's fo'k bomb.
 
Or I could port my Tetris.
 
Battery life: 5 minutes.
 
Nah, it's definitely 20 minutes.
On standby.
 
7:36 PM
gotta keep half of those 48 cores running even in standby so you can receive dem push notificashuns :)
 
Already, even something like my Qosmio with a giant-ass battery and 20 inches just to acccomodate both the battery and graphics card can only survive like 2 hours, and that's after power to the processor is limited to 40% or less and everything goes flat because Aero is disabled.
 
You can keep a grid of 8 x 6 monitors for teleconferencing.
 
There needs to be a significant breakthrough in how batteries are handled before we can shove more computing power in our already bigger-than-my-two-hand smartphones.
Or we can figure out how to take 1/20th of the power we do now to perform computation. I dunno. One or the other.
 
or both!
 
7:40 PM
Indeed.
 
> Not a lot here on Go at Google really. Mostly a general overview of the language, whose major selling point seems to be that it was designed by famous people and is in use at Google.
:D
 
Xeo
Those android events are getting on my nerves, slowly but surely.
 
To conclude my earlier talking about constant time swap and move, am I correct in saying that std::array (and I guess std::tuple) is the only type in the standard that may be expensive to move (only considering stuff with copy or move constructors).
 
Xeo
@R.MartinhoFernandes: Got Clang ToT handy?
 
7:47 PM
@JohanLundberg std::pair.
 
Xeo
Damn.
Any recent Clang build? :P
 
well ok, pair is like tuple...
 
@Xeo No, not at all :/ I am no longer maintaining the VPS I was using.
 
Xeo
Too bad.
Cause I just crashed the clang-bot on #llvm with a small snippet. :(
Something about recursive compilation..
 
@JohanLundberg Almost anything may be just as expensive to move as copy. Just for an obvious example, std::string (using SSO) can be. It's hard (impossible?) to meet vector's exception safety requirements with a similar optimization, or they'd (potentially) have the same problem. The same could apply to most other containers as well. There can also be some issues when/if the containers use different Allocators.
 
7:52 PM
@JohanLundberg A std::array move (copy) is probably quite fast because it is allocated on the stack and has high data locality.
 
Xeo
@StackedCrooked Still O(N) in the size of the array
Compared to O(1) vector move etc.
 
Yeah.
I guess you could always switch to vector if the need arises.
 
@JerryCoffin yes, that's where I come from. chat.stackoverflow.com/transcript/message/6079569#6079569
@Xeo That's what I meant
 
@JohanLundberg Yes, but note that having different allocators is a second, entirely separate issue.
 
Can you have a custom allocator for std::array?
 
7:56 PM
std::array does not use any allocators.
 
Right.
 
Well you can close your eyes and pretend you can, because it doesn't allocate anything anyway.
 
I'll do that then.
 
@StackedCrooked I don't think so -- it doesn't have an allocator parameter at all.
 
I guess stack allocation is basically incrementing the stack pointer.
 
7:57 PM
@StackedCrooked Usually decrementing, but yeah.
 
> For me, in almost every case of segfaults, they arise due to a null pointer dereference. These are basically harmless
dafuq?
 
@JerryCoffin Right, I forget about that.
 
@TonyTheLion why not? ah, harmless
 
To reboot my question from an hour ago, I asked what objects allocate on the heap behind the scenes. I then rephrased the question to be, what objects can move in constant time...
 
@TonyTheLion What's that from?
 
7:58 PM
@TonyTheLion For me in almost every case of segfaults, they arise from dealing with crappy code (usually from GNU).
 
and that seems to be all except array tuple pair
well, pair is constant time in n
 
@R.MartinhoFernandes see link
 
since n is 2
 
My source of segfaults is mostly other people.
:P
 
@JohanLundberg std::tuple and std::array share that characteristic then.
 
8:00 PM
yes... I think valarray is not copyable even...
 
@JohanLundberg That doesn't make much sense.
Constant time is constant time.
 
Xeo
Yea, O(1) range condition testing seems to work.
 
yes. n=2
 
Erm, no.
You can't pick your N for specifying complexity.
 
ah, sure. I know. I just mean, tuple is ordo n. For pair n is 2, hence pair is constant time
 
8:02 PM
:|
For tuple n is n, hence constant time?
 
Xeo
heh
 
For pair, just like for tuple, N is N.
 
tuple size is a constant.
 
what is n?
for pair?
 
8:02 PM
No!
It's N.
 
yes, so there is no ordo N to talk about for pair
 
Perhaps C should have been a better letter.
 
§2.6.2.2/5: "valarray(const valarray<T>&);
The array created by this constructor has the same length as the argument array. The elements are initialized with the values of the corresponding elements of the argument array."
 
Copying a pair takes f(n) time, where f ∈ O(1).
 
@JohanLundberg A non-copyable container type in the standard library? That seems unlikely.
 
8:05 PM
@StackedCrooked using oh_no_you_dont = std::array<std::unique_ptr<int>, 42>;
 
Dammit.
 
@StackedCrooked valarray isn't really a container (but as noted above, it is copyable anyway).
 
Interesting. So, valarray, tuple are O(N), while basic_string (even in case of small string optimization), just like pair, is O(1)
 
@LucDanton You took that smiley out of my pocket...
 
8:09 PM
lol
 
Xeo
@JohanLundberg An n-tuple is O(1).
Since that tuple always has the same size. :)
 
@Xeo But a tuple that holds 10N elements requires 10 times more copies, right? So, shouldn't it be O(N)?
 
no.
 
Xeo
Basically, with limited memory, everything is O(1). Big-Oh is the upper bound. If I didn't get something wrong.
 
@JohanLundberg basic_string doesn't formally allow COW (reference counting with copy-on-write) -- or at least i've been told that, for c++11 with threading considerations. but g++'s implementation still did that a version or two ago. haven't checked lately
 
8:14 PM
Basically, it depends on what N is. (hint: it's not one specific number; it's a thing).
 
@Xeo Yes, it IS the upper bound but unless I--instead--got something wrong, it describes how much more complex the algorithm gets as n increases. So, if N+1 causes 1 more iteration, the upper bound should be N, no?
 
@SplinterOfChaos, when we talk about move and swap, we talk about ordo time
 
@SplinterOfChaos How can a tuple increase in size?
 
What is "ordo time"?
google.com/#q=ordo+time <- not helpful.
 
heh
For algorithms there can be several big O, one for mem usage, one for time etc...
Here we talk about the time
From the standard, Complexity: the time and/or space complexity of the function
 
8:19 PM
Ordo Time looks pretty interesting to me.
 
@LucDanton I don't mean to imply it can, I mean to imply that the cost of copying one is a function of its size. A tuple twice as large will take twice as long. Generally, when I think of O(1), size is irrelevant.
 
Size is never irrelevant.
 
@SplinterOfChaos, I agree. The fact that for tuples the size does not change during the running of a program is not relevant
 
@SplinterOfChaos That goes for any constant.
 
@SplinterOfChaos Right, but tuples objects don't become twice as large. So why does it matter?
 
8:21 PM
Are we actually disagreeing on something or is this just ping pong?
 
std::vector<T> objects can however become twice as large, informally speaking.
 
@LucDanton Tuples become twice as large if you double the number in the code. And that's what the standard must mean when they say linear
 
What.
 
@CatPlusPlus My reaction as well.
 
@LucDanton On the other hand, arrays were always of fixed size too -- but it was quite common (even in languages like Fortran that didn't have dynamic allocation at all) to use O(N), where N was the size of the array.
 
8:23 PM
@StackedCrooked For some reason I thought of Canderous Ordo >.>
 
@JohanLundberg I don't see any complexity requirements for tuple(tuple const&).
 
“A module written by one team may be reused a year later by another team with disastrous results”
 
where you read that?
 
What is this discussion about.
 
@JerryCoffin Aye. It doesn't matter for our purposes, but it's not hard to think of other purposes where it does!
 
@R.MartinhoFernandes Oh..
 
@JerryCoffin Still, VLA-style allocation perhaps?
 
@CatPlusPlus A certain Johan claims that a tuple copy has linear time complexity and not constant.
 
@JerryCoffin In fact, cplusplus.com considers std::array<>::fill an O(n) function.
 
@SplinterOfChaos And that's not wrong. You just have to say what n is.
 
8:25 PM
@StackedCrooked hehe. I do not mean to claim, enlighten me
 
You claim.
 
No, it doesn't have a size argument.
 
@CatPlusPlus Sorry, was mixing up with array.
 
Complexity is constant, because tuples are fixed size. Tuple of size 2 can be only copied from a tuple of size 2.
 
8:26 PM
Which is what the discussion also seems to be about.
 
@CatPlusPlus Then is cplusplus.com wrong to say that the std::array algorithm is linear, because it has a fixed size?
 
So, the standard does not say anything about big O for copy construction of tuple of for example tuple<int,int,int...> N times?
 
cplusplus is wrong about everything.
 
@JohanLundberg Why would it have to do that?
 
@SplinterOfChaos It doesn't say it's linear, it says it's O(n).
 
8:27 PM
It explains the effects, and that should be enough.
 
If vector copy has O(n) complexity and std::tuple coy is O(1) then what about std::tuple<std::vector<T>>?
 
@R.MartinhoFernandes O(n) is linear...
 
Welp.
 
@SplinterOfChaos Basically, no one is right here. Just everyone is very imprecise.
 
Also stop the CS masturbation and concentrate on real problems.
 
8:28 PM
@JohanLundberg Glad we got that cleared up.
 
@R.MartinhoFernandes I'll go with that.
 
@StackedCrooked Luc said It doesn't say it's linear, it says it's O(n).
But does it?
 
@StackedCrooked The cost of copying the tuple is irrelevant when compared to the cost of copying the vector, so it's linear.
 
Or it's still constant time, because only one copy of the vector is made.
@JohanLundberg If n cannot grow, what do you think?
 
8:31 PM
Isn't big-O notation mostly used to define cost of lookup, insertion and sorting? The distinction between O(1) and O(n) is much less ambiguous there.
 
user142019
$ git remote add down foo@example.com:bar.git
$ git pull down pants
2
 
It's used to define complexity of algorithms.
 
@StackedCrooked Nope. It's used to define the growth rate of functions.
 
user142019
Also hi.
 
If you're just going to masturbate, can I suggest some decent (or, better still, indecent) porn instead of cplusplus.com?
 
8:31 PM
Constants are factored out of O, if n is constant, it doesn't matter.
 
I can't imagine a data structure that can copy in O(log n) time.
 
@R.MartinhoFernandes I think it is relevant to think about the functional form of the time it takes to copy a tuple of N integers. The fact that you need to recompile to change N is not relevant to me.
 
And a tuple of 1 int and 1 foo?
 
Copy can degenerate to n^2 or more for complex things.
If you have a vector of vectors or something
It's hard to make a complete copy without making a complete copy.
 
@StackedCrooked That sort of thing becomes entirely possible (and quite interesting to consider) when you're dealing with highly parallel machines (e.g., given infinite processors, what's the fastest you can copy this sort of tree?)
 
8:34 PM
Given a type T, is the cost of auto copy = t; the same for any object t of type T? For std::vector<U>, is the cost of copying from std::vector<U> t(0); the same as copying from std::vector<U> t(42000000);?
 
@StackedCrooked Can't ropes do that?
 
@JohanLundberg It doesn't change, so the time required to copy it doesn't ever change.
 
@JohanLundberg Have you noticed that by restricting yourself to "tuple of N integers", you're talking about what are basically arrays, and not tuples in general?
 
O(1) doesn't mean it finishes instantly.
 
@R.MartinhoFernandes Yes, but I think it is relevant to start with a simple example. It seems we can not even agree on that ;)
 
8:35 PM
Size of the vector can change during the execution.
 
@JohanLundberg It's only relevant to start with a simple example if you can easily generalize it to actual tuples.
 
Size of an array or tuple cannot.
 
I think we can at least agree that copying a tuple of two elements is O(2) = O(1); constant. Copying a tuple of N elements, where N is unknown, can be thought of as O(N). I think we can also agree that N is never unknown, so it's O(1) in most cases.
 
It's not very hard to visualise.
4 mins ago, by Cat Plus Plus
Constants are factored out of O, if n is constant, it doesn't matter.
It never grows, what do you think growth rate is
 
struct foo {
    int x;
    int y;
};
// copying a foo is O(N), because if I double the number of ints it has, time to copy doubles?
 
8:36 PM
It's like asking "what colour is your favourite black horse", jesus.
 
@SplinterOfChaos Known or unknown is completely irrelevant.
@R.MartinhoFernandes yes it is O(n) in the number of int private members
 
No, copying a foo is O(1). The size never changes during execution.
 
@R.MartinhoFernandes Interesting, I'm learning...
 
Assume operation O is O(1). It's actually O(N) because I can perform it N times. QED.
 
@StackedCrooked Please, don't. I'm being sarcastic.
 
8:37 PM
:P
 
GUYS GUYS copying an int is totally O(N) because it might be 4 or 8 bytes depending on platform
 
you agree that std::array<int,n> takes O(n) time to copy?
 
@JohanLundberg That's also worthless.
 
@JohanLundberg No.
Well, yes, but it's O(1) because n is constant.
And constants don't matter.
 
Constants matter.
 
8:40 PM
Not for big-O they don't.
 
If your constants are slow then you are fucked.
 
@JohanLundberg At runtime, let's say N=10. O(10) = O(1). But, if you wanted to know how much worse your algorithm would get if you increased the array size, you'd THEN say O(N).
 
However it's dishonest to group std::array with std::vector as data structures that are linear in cost of copy, like someone did earlier. There is no similarity.
 
Quick sorts and merge sorts O(log n) have different constants, but you don't see them in O() do you
 
From the standard,
Those entries marked “(Note A)” or “(Note B)” have linear complexity for array and have constant complexity for all other standard containers.
 
8:41 PM
Like a give a fuck about what C++ standard says.
 
just after table 96
 
This is getting weird..
 
If you're basing your CS knowledge on a shitty language standard, then I don't know why we're having this discussion.
 
"'_(ˇ-ˇ)_/'"
 
8:43 PM
:|
 
I think the problem with this discussion that big-O notation is not very useful for describing the cost of copies of datastructures. It's nearly always O(n) or O(1) depending on your stance.
 
Well, no.
 
@CatPlusPlus If your basing your C++ knowledge NOT on the standard, ... This is a C++ chat room I entered, right?
 
It's O(n^2) for vector<vector<>> for example.
 
Copy of T is linear to sizeof(T) :P
 
8:44 PM
By this logic nothing a computer does has non-constant runtime, the size is known at some point
 
But yes, if the size never changes during the execution it'll be O(1)
 
Xeo
6 mins ago, by Cat Plus Plus
GUYS GUYS copying an int is totally O(N) because it might be 4 or 8 bytes depending on platform
 
It's not about whether size is known, it's about whether size fucking changes.
 
@CatPlusPlus Or O(N)?
@StackedCrooked "linear to X" only makes sense if X is a variable.
 
Your vector might not grow BUT IN GENERAL CASE the size is not constant.
 
8:45 PM
It changes, sizeof(long) has grown in the last decade.
 
DURING EXECUTION. :cripes:
 
@CatPlusPlus Big-Oh is not about sizes changing, it's about how an algorithm scales with it's size of input
 
I think we really just lack context. If you want to know the complexity of an algorithm as N increases, then it matters not whether N is a compile time constant or not! If you want to know the complexity of your program as the input increases, then obviously the complexity of copying a tuple is irrelevant.
 
@CatPlusPlus So? The whole construct has N elements. Copying it does O(N) copies of the element's type.
 
8:46 PM
And what about copy-on-write? That should count as O(1) because it's independent of size. But that implies that regular copy must be O(n).
 
Whatever.
 
@StackedCrooked COW might be O(1), without COW, O(n). Since O is a maximizing function, and you don't know whether COW will be invoked, O takes the larger value of n.
 
O is not a function.
 
Oh, it is not a function.
 
My god, the point is that copying a string is O(n).
 
8:49 PM
@R.MartinhoFernandes Well, okay, that might be O(n).
 
The point is that you need to say what the fuck is this magical "n" thing.
 
it's the number of times you say "what the fuck"
 
O(infinity)
 
n means number of elements.
 
Well, no, wait, that vector of vectors will actually be O(nm)
 
8:51 PM
@CatPlusPlus oh it's good to see that you're alive again
 
It's bad when latex fails
@Cheersandhth.-Alf I don't know about that.
 
@Rapptz every algorithm is O(ifni)
 
@CatPlusPlus Only if you say that the whole thing has nm elements (or O(nm) elements, or some variation of that).
 
N vectors of M_i elements each.
Or maybe not.
Not very important.
Yeah, it'll be a sum not product, derp.
(You all are still scrubs)
 
8:59 PM
@CatPlusPlus all of a sudden, MSVC can't deal with 2 files called main.cpp in different folders.
">Debug\main.obj : warning LNK4042: object specified more than once; extras ignored"
and then obviously complains about the stuff from the second main.obj not being linked :p
 
Because MSVC sucks.
Also why is there two main.cpp.
 
ask cosh :D
actually, there's 4.
 

« first day (749 days earlier)      last day (4191 days later) »