This kills the Rust programmer

No it isn't and I never said so. In fact including from a library is better than writing it yourself.

So do you usually perverse through each element and push them to the parent list?
Truly, Jow Forums tier.

In systems programming, you need to write optimal data structures, and there is no thing as a data structure that is optimal for all use cases.

not him but actual developers don't play legos so to speak... custom data structures required to be scalable and high performance, on specific hardware configurations, are very common. in actual development. ie where all the "meme degrees" go.

>custom data structures required to be scalable and high performance
Haha, no.
Well may be in languages without polymorphic like C, yes. If you have generics you can implement specialize functions as necessary without reinventing the wheel every time. Pic related.

Attached: 1537771566378.png (1200x1400, 502K)

Fucking hate linked list. Fuck C

Furthermore, in practical use cases a linked list is almost always slower than a vector.

you have never needed to write a custom data structure in a real project, don't bullshit me. and if you really have to, what's the issue with learning to use unsafe wherever required? it's not like a custom data structure will be the bulk of your code, and if you are writing a custom data structure you better be very sure about what you are doing, which means you'll be aware of where unsafe is needed.

it's not like when designing a data structure you'll spend most of the time actually writing the code either, but working on paper

That's why you use an unrolled linked list, dummy.

I know this is bait but I'll reply anyway. Some data structures need this kind of stuff and unsafe blocks in Rust exist for implementing that. If you have proven your data structure and its manipulation safe, then you can include it as a safe part of your project. That's how the stdlib works in Rust : adding stuff built with pointer manipulation then do not care about it in the safe part, namely your project.
6/10 bait

>That's why you use an unrolled linked list
I don't have to, because I use std::vector

will Rust unsafe code really be longer and as ugly as """generic""" C code?

>Rust is a low level systems programming language!
>Ok, I want to write a doubly linked list.
>REEEEEEEEEEE WHY WOULD YOU WANT TO DO THAT JUST USE THE STANDARD LIBRARY WHATS YOUR FUCKING ISSUE WHO THE FUCK WRITES CUSTOM DATA STRUCTURES IN 2018 REEEEEEEEEEEEE

C++ has templates and yet people routinely junk the standard library containers because it's genericity means it doesn't have the performance characteristics that are ideal for the application. U R retarded

i said real developers. with "meme degrees". not only does it come up often, it comes up at least in a quarterly basis.
these are the words of a novice who almost graduated to intermediate dev but never did. its true, but you can't use a giganic vector for everything. across machines you either have a skip list of arrays roughly the size of the hardware's caches, or an insanely hard to implement tree structure that supports parallelization (rare).
everything else is done on a case-by-case basis and is often completely custom.

To be fair im not attacking rust. I never used it. I'm attacking meme developers.

>Dynamic arrays are always better than unrolled linked lists
Dumb tripfag.

What if I want to optimize it to my specific use case hmm?

>or an insanely hard to implement tree structure that supports parallelization
What is the name for this structure?

>WHO THE FUCK WRITES CUSTOM DATA STRUCTURES IN 2018
Indeed. I don't see you implementing `=`, `+`, `printf` `&` every now and then

> genericity means it doesn't have the performance characteristics that are ideal for the application.
These people are not proficient in C++. Generecity in C++ is completely compile time, and comes with utterly 0 runtime cost.
>but you can't use a giganic vector for everything.
Sure, for example I use a data structure called "rope" because it does exactly what I need. Did I write the structure? Of course not, because I don't waste time in reinventing the wheel.
github.com/xi-editor/xi-editor/tree/master/rust/rope
But that's only one rare case. A vector is fine for anything else. Linked lists have almost 0 usage in real life.
en.cppreference.com/w/cpp/language/template_specialization

Now tell my your real experience where you had to specialize for a certain Type.

it differs, usually a mix of B trees with some other structure (skip list of the leafs) or a version of splay. its always custom, ive never seen anyone use a solution that wasn't done in-house...

>A generic BTree/Skip list is "insanely hard" to implement
Ah, the state of Jow Forums

>These people are not proficient in C++. Generecity in C++ is completely compile time, and comes with utterly 0 runtime cost.
Generecity of data structure implementation(not type generosity) is not 0 cost, you will make decisions to reasonably satisfy most cases which can harm the single case.

that provides correctness when multiple agents access and modify it.

why do i even bother...

Ever heard of specialization?
en.cppreference.com/w/cpp/language/template_specialization

As I asked someone else before, give me your experience where you needed to implement a special linked list, I'll wait.

You're missing the point by a mile.
Genericity of data structures doesn't refer to the types of data you can plug into the data structure, but the assumptions about which operations on the data structure are presumed to be most common.
If your application does nothing but insert an element in the middle of a list, then a std::vector is terribly suited for that application. But some kind of linked list may not be.
The access patterns to a data structure are unique to your program and no prefab library is going to perfectly align with your access patterns.

>Linked lists have almost 0 usage in real life.

>But that's only one rare case. A vector is fine for anything else. Linked lists have almost 0 usage in real life.
Caches...

Attached: 1523347294536.gif (250x237, 7K)

LOL
>If your application does nothing but insert an element in the middle of a list, then a std::vector is terribly suited for that application.
It's better than Linked List. Due to >67797826, yes cache locality

this a 1000x this.

LRU cache uses linked list.

>repeatedly inserting into middle of array and shifting shit is good because muh cache locality

Attached: 1474941664043.jpg (248x187, 11K)

I've already explained to you that an unrolled linked list experiences much better cache utilisation than a plain old linked list. Almost as good as an array, except now you have O(1) insertions in the middle.

Also, you are arguing that pushing an item in the middle of the list is more efficient (in pen and paper), but you are not giving me any argument why should I be the one to implement a linked list from the scratch.

Enjoy taking half an year for traversing through to the nth element

>unrolled linked list
Oh so where did your space efficiency concerns go this time?

>Enjoy taking half an year for traversing through to the nth element

If you're inserting anything you're going to have to traverse anyway retard

Yeah, except that for vectors treversing is a breeze thanks to cache locality you stupid fucking frogshitter LOL

Unrolled linked lists are pretty space efficient. The overhead is only one pointer per n elements where n is the number of elements you can fit in a cache line.

Why doesn't Rust std lru use unrolled linked list?
Do you need to know hardware cache line sizes tfor it to be useful?

Yeah. You can implement a portable unrolled linked list in C++ but I think Rust needs construction generics and maybe some compile time evaluation to make it work.

How does c++ do it?

C++ allows you to pass integers as parameters to templates. C++17 also includes a constant for the size of a cache line on the platform you're compiling for.

*blocks your path*
doc.rust-lang.org/std/collections/struct.LinkedList.html

Can't you just call an external C program that implements the doubly-linked list? Or maybe even use Rust to write and compile a C program that implements the doubly-linked list?

Why would you do that if Rust already has linked lists?

>Can't you just call an external C program that implements the doubly-linked list?
lol nice language you have there

performance

Got any benchmarks that shows your non standard linked list written in C is faster than that of std Rust?

>lol nice language you have there
As opposed to a language that lacks linked lists in std?

Spotted the python-fag.

C doesn't need a large standard library - C libraries are everywhere. I'd be surprised if Rust had even 1% as many libraries as C.

Not knowing anything about Rust, I'm taking it for granted that linked lists kill the Rust programmer.

I have a Perl CGI script from 1999 that I'm quite proud of. It parses+sanitizes QUERY_STRING and then outputs and compiles a C program, handing it the QUERY_STRING tokens. My C program, to avoid a profiling-identified bottleneck, outputs and assembles an assembly program.

You kids these days with your Rusts and your Gos don't understand what us old hats understand about writing correct, robust code. That's why I'm the only one in this thread who has suggested the correct solution, which is to output a C linked-list program and compile it. For maximum portability across systems without IPC, I recommend writing node information to a file from the Rust program and reading it in with the C program.

>C libraries are everywhere.
Too bad C has no real package management. So deploying those libraries properly is a hit or miss.
Which is another reason why ctards reinvent the wheel for their fizzbuzz projects.

>Not knowing anything about Rust, I'm taking it for granted that linked lists kill the Rust programmer.
I know, C boomers are quit out of touch with the reality.

>portability
This is indeed a concern, not of Rust but of LLVM. But do realize that perl and perl boomers are obsolete. Because instead of emitting C, people are concerned about emitting LLVM IR

Is this the Unix way?

Also
>I have a Perl CGI script from 1999 that I'm quite proud of. It parses+sanitizes QUERY_STRING and then outputs and compiles a C program, handing it the QUERY_STRING tokens. My C program, to avoid a profiling-identified bottleneck, outputs and assembles an assembly program.
Man no wonder Perl died, any good language is able to achieve that.

>unironically answering to
are you legit retarded?

>unironically

Nice garbage, enjoy your memory fragmentation and cache misses.

>No it isn't and I never said so. In fact including from a library is better than writing it yourself.
Your example is awful for performance.

>>WHO THE FUCK WRITES CUSTOM DATA STRUCTURES IN 2018
Any actual serious project does you fucking retarded moron.

okay I'll bite, as a relatively experienced rust programmer
safe:
use std::rc::Rc;
use std::cell::RefCell;

struct Node {
data: T,
next: Option,
prev: Option,
}
impl Node {
fn new(data: T) -> Rc {
Rc::new(RefCell::new(Node{data: data, next: None, prev: None}))
}
}
trait Append {
fn append(&mut self, &Rc);
}
impl Append for Rc {
fn append(&mut self, node: &Rc) {
self.borrow_mut().next = Some(node.clone());
node.borrow_mut().prev = Some(self.clone());
}
}
impl Append for Option {
fn append(&mut self, node: &Rc) {
match self {
Some(s) => s.append(node),
None => {},
}
}
}

fn print_vals(n: Option) {
match n {
Some(n) => {
println!("{}, ", n.borrow().data);
print_vals(n.borrow().next.clone());
}
None => {},
}
}

fn print_vals_reverse(n: Option) {
match n {
Some(n) => {
println!("{}, ", n.borrow().data);
print_vals_reverse(n.borrow().prev.clone());
}
None => {},
}
}

fn main() {
let mut n = Node::new(1);
n.append(&Node::new(2));
let m = Node::new(3);
n.borrow_mut().next.append(&m);
print_vals(Some(n));
print_vals_reverse(Some(m));
}

it's fairly easy to write idiomatic rust code behind an API layer, so that the end user doesn't have to see anything too outlandish. Rust is built off of abstractions.

unsafe:
use std::ptr::*;

struct Node {
data: T,
next: *mut Node,
prev: *mut Node,
}

unsafe fn print_vals(n: *mut Node) {
if !n.is_null() {
println!("{}", (*n).data);
print_vals((*n).next);
}
}
unsafe fn print_vals_reverse(n: *mut Node) {
if !n.is_null() {
println!("{}", (*n).data);
print_vals_reverse((*n).prev);
}
}

fn main() {
unsafe {
let mut n = Node{data: 1, next: null_mut(), prev: null_mut()};
let mut n1 = Node{data: 2, next: null_mut(), prev: &mut n as *mut Node};
n.next = &mut n1 as *mut Node;
let mut n2 = Node{data: 3, next: null_mut(), prev: &mut n1 as *mut Node};
n1.next = &mut n2 as *mut Node;
print_vals(&mut n as *mut Node);
print_vals_reverse(&mut n2 as *mut Node);
}
}

This is pretty much exactly the same as any doubly-linked list you'd write in C. Unsafe rust is basically a more expressive and more typesafe C.

>Too bad C has no real package management. So deploying those libraries properly is a hit or miss.
And yet C++ also does not. Also, if your system isn't pure retarded garbage (like Windows), you have a system package manager already that provides you a huge amount of libraries.

>enjoy your memory fragmentation and cache misses.
I won't, I rarely, very rarely use Linked Lists.

>Your example is awful for performance.
Prove it. Give me an actual benchmark instead of pulling shit out of your faggot ass.

>Any actual serious project does you fucking retarded moron.
Show me 3 projects where they reinvented linked lists.

Double linked list is simple case for Graph data structure, looks like Mozilla will implement garbage collector in Rust to implement DOM in Firefox.

>Prove it. Give me an actual benchmark instead of pulling shit out of your faggot ass.
You're asking the fucking system to allocate memory for you retard. Of course it's going to cause cache misses, memory fragmentation and generally perform like garbage.

>C++17 also includes a constant for the size of a cache line on the platform you're compiling for.
Please elaborate.

You can't reserve values without asking the system to allocate memory for it. What's your point?
>oh no syou need to allocate memory for a data structures
LMAO

tripfagging should be a bannable offence; there has never been a non-retarded tripfag on this board.

Which of my post BTFO'd you so badly?

>You can't reserve values without asking the system to allocate memory for it. What's your point?
The point is that every entry in your linked list is calling new() instead of just making a big allocation and then writing your own memory manager to use that memory.

This is literally the most basic optimisation you could possibly make for any program.

Making a big allocation is only useful when the memory are subsequent, you fucking dolt. Utterly pointless for linked lists.

>Utterly pointless for linked lists.
That isn't true, linked lists often serve as the basis for more complex data structures like binary trees, stacks/queues etc.

This is why your claim of "lol I almost never use linked lists anyway xDDDD" is retarded.

>Making a big allocation is only useful when the memory are subsequent, you fucking dolt.
Any big data structure is going to want subsequent memory you fucking dumbass, even in the case of a linked list.

>Any big data structure is going to want subsequent memory you fucking dumbass
Demonstrably false. wtf

It literally isn't false. If you want a performant data structure then you want subsequent memory allocations to avoid cache misses.

Again, this is literally the most basic optimisation you could possibly make in any program.

>isn't false
Wrong again.
Create a Linked list of 10000 elements, and print out the addresses of each of those elements.
PROTIP: elements are scattered all over the vast pool of heap

Linked lists don't have subsequent elements, which is why no one bothers reserving a big chunk like array/vectors.
For reference see
cplusplus.com/reference/forward_list/forward_list/
doc.rust-lang.org/std/collections/struct.LinkedList.html
No API for pre-allocating memory because it simply does not make sense. Educate yourself.

>Tripfag name mangling c++ shill shutting up the thread
Why am I not surprised

I got tired of your shit FUD, find a better one, OP.

>PROTIP: elements are scattered all over the vast pool of heap
Only if each element has been allocated through the system memory allocator, which is my fucking point you retard. It's bad for performance because it induces cache misses.

>Linked lists don't have subsequent elements
No, but it has a link to other nodes, and if those nodes are scattered all over memory then you have a performance problem because it induces cache misses. If a linked list implementation then serves as the basis for binary trees, stacks/queues and other data structures then you have a fucking problem with cache misses

>Educate yourself.
No, you educate yourself you fucking moron.

FWIW, proposed solution: Implement a memory allocator for your data structure needs and then if necessary data structures that make use of it.

This is why Rust is the monkey language
Rust can't be used to teach computer science
Rust spreads fud on how logic is dangerous
Rust promotes using an api instead of building your data structures
Rust is anti freedom

Rust sucks

Holy shit this is hilarious so you are saying you write an allocator in order to be using linked lists "without cache misses"? hahahaha rofl

Why don't you write your own language and a compiler, fizzbuzz autist?

>Rust promotes using an api instead of building your data structures
See
Another Jow Forums autist CAVED. lol because le'ts be honest. Ctards reinvent the wheel because the wheel is not in their standard.
How many times have you seen a Ctard re implement shit like puts() or printf()? Never? I wonder why hahahaha

>Holy shit this is hilarious so you are saying you write an allocator in order to be using linked lists "without cache misses"? hahahaha rofl
AND OTHER DATA STRUCTURES, how retarded are you that you do not understand the sentence "If a linked list implementation then serves as the basis for binary trees, stacks/queues and other data structures"? Because that is fairly common.

>let me just be retarded and not allocate my memory properly

100% standard within video game development to have a custom memory allocator so you don't end up with massive memory fragmentation and cache misses, because it has a direct negative effect on performance.

I bet you write Pajeet tier slow ass software that makes a new memory allocation every time someone presses a button. Holy shit, you are god damn retarded.

>I bet you write Pajeet tier slow ass software that makes a new memory allocation every time someone presses a button. Holy shit, you are god damn retarded.
I write software that exists, because I don't write NxM amount of memory allocator for N number of types and for M number of data structures.
Sorry to bother you.

en.cppreference.com/w/cpp/thread/hardware_destructive_interference_size
Ignore the standard-ese - they're the size of your cache line and the offset between set cache lines in the same set.

>your linked list sucks because it doesn't use the allocator I wrote
kek

>he genuinely thinks the memory allocator needs to care about the data type
Oh wow, you really are fucking retarded

>I write software that exists
Nah, you're straight out of some bootcamp or something.

>you have never needed to write a custom data structure in a real project, don't bullshit me
lmao

>he genuinely thinks the memory allocator needs to care about the data type
>Oh wow
What's that? You don't specially specialize your allocation algorithm for some hypothetical special type by hand? You don't belong here, pajeet LOL
Now why don't you go back to your fairy tale allocator that you work on in your imagination?

Thanks. They really tried to give these variables the worst possible names imaginable.

>What's that? You don't specially specialize your allocation algorithm for some hypothetical special type by hand?
No, because memory has no fucking concept of "data type", and just stores bits. Only the CPU has that concept (of limited scope).

There is 100% never any need to write a memory allocator that knows the data type or even remotely cares about it. All it needs to know is the size to be allocated and that's it.

>Now why don't you go back to your fairy tale allocator that you work on in your imagination?
Real, professional high performance projects write their own memory allocator all the time you retarded mongrel.

>professional high performance projects write their own memory allocator all the time you retarded mongrel.
Name 3.
>OH NONONONONONONONONO
>*WHEEZE*

>Name 3.
Literally ANY video game engine. No joke.

FWIW it's detailed in books like Game Engine Architecture too.

Can you guys stop feeding that retarded tripfag already?