K-ballo changed the topic of #ste||ar to: STE||AR: Systems Technology, Emergent Parallelism, and Algorithm Research | stellar.cct.lsu.edu | HPX: A cure for performance impaired parallel applications | github.com/STEllAR-GROUP/hpx | Buildbot: http://rostam.cct.lsu.edu/ | Log: http://irclog.cct.lsu.edu/
K-ballo has quit [Quit: K-ballo]
shubham has joined #ste||ar
heller1 has quit [Quit: Idle for 30+ days]
sbalint[m] has quit [Quit: Idle for 30+ days]
shubham has quit [Quit: Connection closed for inactivity]
jehelset has joined #ste||ar
jehelset has quit [Remote host closed the connection]
jehelset has joined #ste||ar
K-ballo has joined #ste||ar
<gonidelis[m]>
K-ballo: how views achieve O(1) copy, move and assign? I know that they don't own the elements, but is it just it?
shubham has joined #ste||ar
<K-ballo>
gonidelis[m]: what else is there?
<K-ballo>
what do you think O(1) copy means?
<gonidelis[m]>
K-ballo: it means copying the first element? aka copying the ref?
<K-ballo>
ping me once you've read that and i'll expand
<gonidelis[m]>
hm... if you mean just the section of asymptotic complexity, I am already familiar with big O
<K-ballo>
ok, so what does O(1) mean then?
<gonidelis[m]>
the computation happens immediately
<gonidelis[m]>
at one step
<gonidelis[m]>
constant time
<K-ballo>
not quite, but... acceptable? maybe?
<K-ballo>
the computation can still take hours and be O(1)
<K-ballo>
the execution *order* is constant, not the execution time
<K-ballo>
what it means is that the execution time doesn't depend on n, for algorithmic complexity guarantees n is the number of elements in the range
<gonidelis[m]>
yeah ok
<K-ballo>
O(1) copy for a view thus means the copy takes as much time whether the view is empty, ranges over a few douzen elements, or a million billion elements
<gonidelis[m]>
yeah exactly. That's what I understand
<K-ballo>
the cost of the view copy is the cost of copying all the view's state
<gonidelis[m]>
ok now it gets juicy...
<K-ballo>
what state can a view have that depends on the number of elements in it? (none, by definition)
<K-ballo>
views don't own the elements, so copying the state of the view does not incur any element copy
<gonidelis[m]>
!
<gonidelis[m]>
ok tell me when your explanation is over so I may ask....
<K-ballo>
just ask
<gonidelis[m]>
sorry was having lunch.
<gonidelis[m]>
K-ballo: why is it that views' state does not depend on num of elements?
<K-ballo>
that's not really true
<gonidelis[m]>
sounds to me either like some scam or some algorithmical brakethrough (i know it's neither of those two)
<K-ballo>
"scam"?
<gonidelis[m]>
ok i will tell Ali to delete this quote ;p i am just emphasizing on how the hell do views do all this thing without just being plain references
<K-ballo>
what's "all this thing" that views are doing
<K-ballo>
views are for all intent and purposes reference-like objects
<gonidelis[m]>
move copy assign
<gonidelis[m]>
in O(1)
<K-ballo>
what do you think makes O(1) copy challenging?
<K-ballo>
remember that O(1) does NOT mean "in one step"
<K-ballo>
it can be 700 hundred steps and take hours to execute, still be O(1)
<gonidelis[m]>
for(i=0; i<700;){arrayB[i] = arrayA[i]} sounds like a 700 hundred steps and is definately not O(1)
<gonidelis[m]>
how does one include 700hudred steps witout being o(1)
<gonidelis[m]>
?
<gonidelis[m]>
and what i was going to say is, copying multiple things could be achieved in o(1) if using the by reference technique... but mutating... that sounds a whole lot of different
<K-ballo>
yeah, that's not how asymptotic complexity works
<gonidelis[m]>
i would sum up my understanding as "views are just recipies that predetermine future states"
<K-ballo>
what's your N?
<gonidelis[m]>
good question
<K-ballo>
if you copy an array of 700 elements where N is the number of elements in the array, the copy is O(n)
<gonidelis[m]>
yeah exactly
<K-ballo>
if you copy 7 arrays of 700 elements, the copy is O(7)
<K-ballo>
where N is the number of arrays
<K-ballo>
if you copy one struct with 7 arrays of 700 elements where N is the number of structs, the copy is 1
<K-ballo>
in algorithmic complexity guarantees, n is the number of elements in the range
<gonidelis[m]>
!!!!
<gonidelis[m]>
so it's all about keeping your things packed in a SoA
<K-ballo>
no, not at all
<K-ballo>
it's about understanding asymptotic complexity
<K-ballo>
you should go and have a read at all the material linked earlier
<gonidelis[m]>
the wikipedia page
<gonidelis[m]>
?
<K-ballo>
sure, that's a good starting point, it links a few other relevant pages too, and external articles
<K-ballo>
for algorithmic complexity guarantees, n is the number of elements in the range
<gonidelis[m]>
<K-ballo "you should go and have a read at"> will I have finished by May3rd ? ;p
<K-ballo>
N is the number of elements, views don't own their elements, so views don't make N copies of those elements
<gonidelis[m]>
ahhhhh!!!!
<K-ballo>
views also can't, by definition, have N of anything in its state (or they wouldn't be copyable in O(1))
<K-ballo>
they can only have a constant number of anythings in it
<gonidelis[m]>
shiiitt
<gonidelis[m]>
say one struct?
<K-ballo>
struct is irrelevant, can be 3 structs
<K-ballo>
the order of any constant is 1
<gonidelis[m]>
say 700 arays, then?
<K-ballo>
a view can have 700 arrays in it, and copy those on assignment, as long as it always have 700 arrays in it independent of the elements in the range
<K-ballo>
copying a constant number of arrays is O(1)
<K-ballo>
since the number of arrays does not depend on N
<K-ballo>
O(f + C) === O(f)
<K-ballo>
hence O(700) = O(3) = O(1)
<K-ballo>
this is basic asymptotic complexity stuff, but by no means it is easy simple stuff
<K-ballo>
and you will need to understand it to operate with algorithm, as the complexity guarantees of the interfaces are defined in terms of asymptotic complexity
<gonidelis[m]>
no no! i do understand your adymptotic complexity argument
<gonidelis[m]>
but i sure don't understand the trickery behind views
<K-ballo>
there's no such trickery whatsoever
<gonidelis[m]>
it's like you are saying just because elements are constant, copy is O(1)
<gonidelis[m]>
num of elements*
<K-ballo>
yes.. constant as in independent of N... that's exactly what asymptotic complexity says
<gonidelis[m]>
but then again a const std::vector<int> a[50] has const num of elements
<K-ballo>
no
<gonidelis[m]>
how?
<K-ballo>
again, what's your N?
<gonidelis[m]>
my N is 50
<K-ballo>
in algorithmic complexity guarantees the N is the number of elements in the array
<K-ballo>
no, not any one instance
<gonidelis[m]>
my N is the num of elements*
<K-ballo>
check the links again
<gonidelis[m]>
i am hurting right now
<gonidelis[m]>
ok
<K-ballo>
O(n) is complexity when n tends to infinity
<gonidelis[m]>
in no computer-programmatic case shall n tend to infinity!
<K-ballo>
lol
<gonidelis[m]>
what?
<K-ballo>
is that relevant somehow?
<gonidelis[m]>
are you joking?
<K-ballo>
definitely not
<K-ballo>
remember this is *order*, not *time*
<gonidelis[m]>
are you asking me whether ranges::views are relevant to programming?
<K-ballo>
no
<K-ballo>
btw we have inifinite views, as an aside
<K-ballo>
we do not have infinite containers
<K-ballo>
it's all irrelevant to big O anyhow
<gonidelis[m]>
oh thanks! now everything is perfect in my head.
<gonidelis[m]>
who has infinite views?
<K-ballo>
C++
<gonidelis[m]>
how do the guyes who have infinite views, have infinite views?
<K-ballo>
go read the material on asymptotic complexity, it takes a while for it to sink in
<gonidelis[m]>
guys*
<gonidelis[m]>
ok
<K-ballo>
you just.. do..
<gonidelis[m]>
ah ah ah ah!!!!
<K-ballo>
remember the storage of views doesn't depend on the number of elements
<gonidelis[m]>
i got it
<gonidelis[m]>
you cobine views with view adaptors
<K-ballo>
so it's possible for a view to have infinity elements in it
<gonidelis[m]>
that's what you are saying
<gonidelis[m]>
?
<K-ballo>
not really, no
<gonidelis[m]>
oh you mean sth like views::ints
<gonidelis[m]>
we have infinite ints here
<K-ballo>
sure
<gonidelis[m]>
<K-ballo "remember the storage of views do"> exactly my point: what is it stored when we want to store a view?
<K-ballo>
or like repeat(X)
<gonidelis[m]>
yeah exactly
<K-ballo>
that's entirely view specific, but in no case can it depend on the number of elements
<K-ballo>
for repeat(X) we 'd store X
<gonidelis[m]>
lol
<gonidelis[m]>
and where is the repeat information?
<gonidelis[m]>
who keeps that?
<K-ballo>
what "repeat information" is there?
<gonidelis[m]>
the keyword repeat
<K-ballo>
you mean the type?
<gonidelis[m]>
translates into something
<gonidelis[m]>
auto a = repeat(C)
<K-ballo>
the type exists only in the compilers representation, during compilation time, it isn't stored anywhere
<gonidelis[m]>
what does the assembly think a is?
<K-ballo>
a type is not state
<K-ballo>
the assembly thinks it's a bunch of words
<gonidelis[m]>
"a" is not type
<gonidelis[m]>
the compiler
<K-ballo>
the assembly always thinks everything is a bunch of words
<K-ballo>
`a` the C++ variable is either a registry or a memory location for assembly
<K-ballo>
you're only going to confuse yourself further going that way
<gonidelis[m]>
so it's a semiregular type. a type of things that might exist or don't
<gonidelis[m]>
and we don't give a shit how the compiler will feel about that (at least view-wised, for sure we did when we created std::optional or semiregular types)
<K-ballo>
no need to get rude
<gonidelis[m]>
haha
<gonidelis[m]>
i am joking
<gonidelis[m]>
sorry if i offended you though
<gonidelis[m]>
i appreciate your help
jehelset has quit [Remote host closed the connection]
shubham has quit [Quit: Connection closed for inactivity]
shubham has joined #ste||ar
shubham has quit [Quit: Connection closed for inactivity]