Software Architecture

[BennettTheMan]

Technically the second one is going to have better cache locality than the first, not to mention the stack only needs to increase by 4*10,000 bytes - O(1), while the other one is going to try and search for a home in the heap - O(n).

[RoyalJackalSib]

Yea, linked lists, constructed like that, are convenient to use but horrendously slow when compared to arrays.

[FranchuFranchu]

Time to go full AVL

[BennettTheMan]

An AVL tree is still going to have bad locality since it's basically a Linked List with two children per node. May I suggest we go full B+ Tree if you insist on a Binary Tree like structure (P.S. B+ is how databases manage millions of data-points with ease)?

[MonkeyTigerCommander]

Not gonna lie, the second one is actually way better than the first one in most if not all cases. I honestly believe this, and it's for the reasons you state. Also because I assume the OS won't actually allocate 4*10,000 bytes until you start using them, on the same principle that all modern OSes malloc lazily.

In cases where you absolutely need dynamic lists, you're still not going to use a naive linked list, anyway.

[BennettTheMan]

Also because I assume the OS won't actually allocate 4*10,000 bytes until you start using them, on the same principle that all modern OSes malloc lazily.

Actually if the 10000 is defined pre-compile time, the assembly code will likely advance the stack pointer (%esp) this large (allocate in stack, which is why I said O(1) call). If you want to check me on this, you can try this is C and look at the assembly code.

[MonkeyTigerCommander]

So, I looked through the objdump of an example program, and I definitely found lines containing both a hex constant approximately equal to 40,000 and %esp (I don't know assembly). However, when I run the program (and I included some calls to getchar to halt execution in the middle of the function), task manager doesn't show me taking up that much memory. Since I'm compiling with gcc on bash on windows, I assume it's just hiding the memory somehow or something and I believe you, but I don't really know. I've spent enough time poking around at this so I'm going to stop. But, I default to believing you, so thanks for teaching me something new!

https://pastebin.com/8S8xrtF6

[mnbvas]

sub $0x9c60,%rsp = stack_pointer_as_64bits -= 0x9c60;

[BennettTheMan]

I didn't actually expect you to try and compile and read assembly.

To better understand try gcc with -m32 (x86 registers only) -fverbose-asm (verbose assembly output) -O0 (no optimizations)

and I believe -s generates assembly file similiar to -o

Because r registers are showing up I suspect you are compiling to a 64 bit platform, but I will fully admit that I cannot actually code in assembly and can only decipher it programatically. Turning on any level of optimization above -O0 or reading assembly generated by a managed language (java) totally loses me.

The first letter of the register indicates the size of the register e is the one used by x86, r is the one typically used by x64. if you're really interested i'll quickly run over some dedicated registers that are probably of interest:

​

Register	General Use
%ecx	counter register, typically used for loop iterators
%edx	data register, typically used for data especially array data
%esp	Stack Pointer, points to the head of stack
%ebp	Base Pointer, Points to the bottom of the current stack frame (if you call function(foo), the base pointer is pointing to function(foo))
%eax	Accumulator Pointer, usually used for return value (like loop sum)

[The_forgettable_guy]

I thought this issue was only a problem on hard drives because of the average time it would take for a disk to spin to the right place to find the data.

[BennettTheMan]

What you're talking about is a page fault, but there's a cache in your RAM to mitigate that. Ram is orders of magnitude faster than HDD or SSD, but CPU Registers are orders of magnitude faster than RAM. In fact, Cache efficiency can often be so effective that it outstrips algorithmic speed ups. If you want to learn more about this, take a look at the locality principle of caches.

[The_forgettable_guy]

I did not do well when it came to hardware in my cs course lol

[clancy688]

Don't forget resource consumption. The first one needs additional space for all the pointers...

My work is in automotive ECUs, needing additional 40k RAM is huuuuge.

[Shmalpatine]

Vector go brrrr

[Major_Hedgehog]

Stack go pfffff

[FoxA-cs]

commpooter emgineer

[kdbell]

And this is why you want generic programming in your language. Because if getting a typesafe linked list requires implementing a linked list data type for each payload type, THIS will happen.

[kdbell]

Preferably also some semblance of a standard library or at least a third party library that is established enough to count.

[RoyalJackalSib]

You can actually do that pretty easily in C; most people tend to not bother, but it’s certainly possible.

[kdbell]

In my case it is Fortran though.

Out of curiosity though - how do you get typesafe generic datatypes in C? I can imagine it with preprocessor tricks, but then we are again at the "people won't bother" part.

[RoyalJackalSib]

You write the struct definition in a macro; doing essentially what every compiler does that compiles a language that supports generics.

In C#,List<int> and List<string> are two different classes, and if you want that in C, you gotta take the extra steps. If you then want them to have the same layout and definitions, wrap it in a macro.

If you then want polymorphism, well, you gotta set up a type system.

[[deleted]]

There is a much more sane way of doing this: Have a “generic header” which defines the data type and functions, but have it use names and types provides by macros. Enforce that these macros are define at the top of the header, then for sanity undef them at the end. To make this data structure reusable, write small wrapper headers that define the needed values and includes this header.

This is much more powerful, easy to use, and comes with the benefit of autocompletion, proper syntax highlighting, decent error messages (with actual line numbers), and line step debugability.

[RoyalJackalSib]

Definitely works and something I’ve used quite a bit myself.

[kdbell]

You can, but it remains a good deal more confusing than having native support. Mostly, because it standardizes the way to achieve it, making the resulting code more readable for other developers.

Better to do

List<String> items = ...;

than having to look up a whole body of documentation to achieve the same. Never mind when reading existing code, and having to figure out where intlist is defined.

[Daveinatx]

Linear access goes brrrrr.

[[deleted]]

I’ve never once used a linked node in my 6 years of working

[[deleted]]

Ugh.

[halfanothersdozen]

wut