[ 3 / biz / cgl / ck / diy / fa / g / ic / jp / lit / sci / tg / vr / vt ] [ index / top / reports / report a bug ] [ 4plebs / archived.moe / rbt ]

Due to resource constraints, /g/ and /tg/ will no longer be archived or available. Other archivers continue to archive these boards.Become a Patron!

/g/ - Technology

View post   

[ Toggle deleted replies ]
File: 23 KB, 270x354, xBjarne2018.jpg.pagespeed.ic.Azl4HkfGcY.jpg [View same] [iqdb] [saucenao] [google] [report]
65967827 No.65967827 [Reply] [Original] [archived.moe] [rbt]

How are vectors written in C? Is it even done? I have a hard time believing developers are satisfied with linear access lists and size constrained arrays.

>> No.65967834

Please return to CS101 if you're asking this question seriously.

>> No.65967852

Hey buddy, not sure what college you went to, but C is rarely taught these days. Especially at the entry level.

>> No.65967896


>> No.65967951

Ellaborate yourself

>> No.65967971

What? My college is mostly Java but C is a very close second

>> No.65968001

Do you go to some third world embedded systems trade school?

>> No.65968019

A state university

>> No.65968038

What school? I went to Old Dominion where I learned C++. I was one of the 4 students at my school who somewhat knew C.

>> No.65968059


>> No.65968085

Are Python list arrays vectors under the hood?

>> No.65968177

Assuming this isn't bait, you should know that C and C++ are different languages with different use cases. Although C++ is (basically) a superset of C with classes, stl, etc. it is not normally written the same way as C. (Note: many universities teach C++ as "C with classes", which is fine I guess but doesn't really teach the power of the newer C++11 ,14, or 17 constructs, which are used in industry code. Not always used, but they are used more often than not in my experience.)

To help this make sense, think about making a char[100]. In both C and C++, you are allocating 100 bytes on the stack of data you can do whatever you want with. You can clearly see how this is a powerful ability, and the use is clear. It may help to explain that an array is just a contiguous block of data with n elements, where it is sizeof(type)*n bytes long (excluding padding). You could explicitly write binary to a char array and then typecast it as a double, you'll get a double.

A C++ vector on the other hand, is a data structure that needs far more data when you create one typed char with 100 members. There is overhead in creating the vector, storing it, and resizing it. It is far easier (and often times more reliable), but you've added quite a bit of code, and that adds time and memory.

On modern computers the time/memory isn't really a huge deal, but it should be fairly clear now why C programmers don't just build vectors when they want to store data. An array and a vector are used for different things, and even though there is overlap in their uses that doesn't mean one will always be preferred over the other.

>> No.65968190

Good question, I really have no idea it's so complex. It doesn't remind me of a linked list and you can access items directly. Unless it iterates sequentially.

>> No.65968214

python lists are linked lists and the arrays from numpy are dynamic arrays aka vectors.

source: pure guess

>> No.65968283

So is there any evident case of vectors being used in C for their search time and rescalability, or is it just generally avoided?
I do not think they're lists, click link on

>> No.65968287

No... Python lists are O(1) random access.

>> No.65968302 [DELETED] 

just look up what a vector is
then write it
they're I've if the easiest data structures

how much spoon-feeding do you need? If you're this retarded you should change fields

>> No.65968305


>> No.65968315

Same way it is written in C++.

>> No.65968326

He's just going to Google it the same way you could have dummy

>> No.65968341

just look up what a vector is
then write it
they're one of the easiest data structures

How much spoon-feeding do you need? If you're this retarded you should change fields

>> No.65968343

Maybe I just wanted to see Anon provide an example out of curiosity, and proof that he knew what he was talking about. Why the hostility?
Idk about that, C doesn't have methods.

>> No.65968351

Meant to reply to

>> No.65968365

It's in the source code boi, someone just posted it.

>> No.65968373


>> No.65968374

lol that was me, didn't realize they provide d big O in the comments.

>> No.65968381

Sure it does

vector * v = vector_new();

vector_push_back(v, 5);

printf("length: %d\n", vector_size(v));
int x = vector_get(v, 0); // x = 5


>> No.65968398

>on the heap

>> No.65968411
File: 29 KB, 633x758, 318271da980706f7a18a811c3456a77d.png [View same] [iqdb] [saucenao] [google] [report]


>> No.65968425

static methods are still methods
use meme function pointers if you want polymorphism

>> No.65968427

No, mainly because since C++ is (almost) a superset of C, if you want vectors you just write C++. I went a little overboard explaining it looking at that block of text lol.

Vectors are used for a couple reasons: resizeability, reliability, and flexibility/ease of use. The question is do we need that when we are writing pure C as opposed to C++? We don't. C is used in production for things like hypervisors, operating systems, embedded systems (among others). All of these systems memory and time are serious concerns. Say you are writing an emulator where the host machine's cpu runs at 4x the clock rate of the guest machine's, this means you have 4 clock cycles to emulate the guest machine's instruction to make it seem like the emulated guest machine is running at normal speed. Thats not a lot, and the code you are writing better be fast, you might even just want to write some assembly for that. You better fucking believe a vector resize operation takes a few more than four clock cycles. Don't even get me started on how absolutely fucking fast operating system code needs to be relative to user level code.

When writing these low-level applications speed, memory and robustness are the most important parts of the software. C++ is used in user level code because it has these constructs that make it easier for programmers to get the software in production, but also add slowdown and memory usage that the end user doesn't care too much about.

Also it should be noted that C++ is still faster than a lot of stuff since its compiled, don't be fooled into thinking that its slow. Its just not fast enough when you use stl for low level stuff (in most cases).

>> No.65968436

vector v;

vector_push_back(&v, 5);

printf("length: %d\n", vector_size(&v));
int x = vector_get(&v, 0);


>> No.65968444

A C++ vector is just a size-constrained array under the hood that is intelligently realloc'd (or whatever bastardization is the c++ equivalent) as needed.

In C, you'd use a third party library or implement it yourself.

>> No.65968446

meant for >>65968398

>> No.65968474

Its an very OP vector template that accepts literally any type

and yes every python noobs wield this power right out of the box

>> No.65968588

Are you retarded? Just about every operating systems and concurrent programming course in the US is taught in C.

>> No.65968617

Just because ITT Bombay doesn't teach using C doesn't mean actual universities don't.

>> No.65968645

What kind of shitty uni doesn't teach C?

>> No.65968651


Linked lists are terrible for caching


>> No.65968686
File: 137 KB, 340x340, 729.gif [View same] [iqdb] [saucenao] [google] [report]

> Old Dominion
> ranked #231-300 on USNews
Maybe that's why nobody at your school knew C.

>> No.65968700

don't modern processors all have markov cache predictors?

>> No.65968757
File: 121 KB, 1000x1100, 1495398141882.png [View same] [iqdb] [saucenao] [google] [report]


>> No.65968759

They are extensible arrays iirc.

>> No.65968778

> he doesn't use unrolled linked lists

>> No.65968917

checking in

>> No.65968945

>allocates 8 bytes per element
It fosters ignorance and waste of resources. Use https://docs.python.org/3/library/array.html instead.
It was funny seeing the "sum the primes under 2 million" threads on /g/, where Pythonistas were using lists for a bool array in their sieve. It takes ~7.45GiB of RAM just to hold a bool array of 1 billion elements using lists, compared to 0.93GiB for a char array.

>> No.65968980

> he doesn't know about unrolled linked lists

>> No.65968983

I mean that sounds like something I just wouldn't want to use python for anyway

>> No.65969030

>he doesnt utilize every single bit

>> No.65969055

Not applicable to Python.
But you can optimize any language, and understanding of algorithms like prime sieves is language independent. The point is, a bool array doesn't need 8 bytes allocated per element, and one should know that. Languages like Python abstract too much, and give a poor understanding to beginners.

>> No.65969131

>what is heap

>> No.65969148

What C++ offers over C in this area is restricting access patterns (no private in C), ease of writing containers (template metaprogramming) and member function call syntax.
It doesn't make any more datastructures possible.

That said datastructure use tends to be more restrained in C. Usually because the areas where you use C you value predictability. I can't explain it quickly but if you use advanced datastructures you often give up the allocation to the library.
Of course there's ways around this...

>> No.65969153
File: 57 KB, 588x351, Screenshot_2018-05-16_19-34-11.png [View same] [iqdb] [saucenao] [google] [report]

Rate my bitsieve
$ time python3 -c 'import primes; print(sum(primes.bitsieve(2*10**6)))'

real 0m0.712s
user 0m0.711s
sys 0m0.000s

>> No.65969186

at my uni the first year is almost entirely Scheme.

>> No.65969236

good now rewrite it in C

>> No.65969237

MIT? We do a little scheme at Rutgers, I think. I'm taking a principles of programming languages course next semester and I think they use scheme for the functional programming part.

>> No.65969264
File: 152 KB, 466x492, 1508965388120.png [View same] [iqdb] [saucenao] [google] [report]

>he thinks I know C

>> No.65969274

>So is there any evident case of vectors being used in C for their search time and rescalability, or is it just generally avoided?
If you're using C over something else, such as C++, then you're usually doing so for performance. Vectors are nice for the programmer because you can use it for a lot of things. But if you're writing C you'd probably rather customize your search for the specific task and memory structure.
If you wanted rescalability, you'd use realloc (and/or maybe VLAs). It takes a bit more time, but once you use the task to define bounds it's easy for realloc to provide the same rescalability functionality as vectors with much better performance.

>> No.65969282

It also has the advantage that it automatically deletes its heap contents when it goes out of scope and that the underlying array can be passed to C functions. C++ vectors are just comfy.

>> No.65969294

Verctor[Number of vector][U][V][W]


>> No.65969353

>he cant write a basic C program

>> No.65969416

You can do something like this https://pastebin.com/txQbd6i7

size_t *test = load_xarray(0, sizeof *test);
assert(xarray_size(test) == 0);
for (size_t i = 0; i < N/2; ++i) {
test = xarray_expand(test);
test[i] = i;
assert(xarray_size(test) == N/2);
for (size_t i = 0; i < N/2; ++i) assert(test[i] == i);
test = xarray_resize(test, N);
memset(test + N/2, 0, sizeof (size_t [N/2]));
assert(xarray_size(test) == N);
for (size_t i = 0; i < N/2; ++i) assert(test[i] == i);
for (size_t i = N/2; i < N; ++i) assert(!test[i]);

>> No.65969563

This board is for Americans, friend.

>> No.65969586

No, they are arrays that double in size as space needs grow, more or less. I believe there are alternate implementations that use linked lists but CPython uses arrays.

>> No.65969690
File: 25 KB, 405x583, 1499113774343.jpg [View same] [iqdb] [saucenao] [google] [report]

>it's actually an array

>> No.65969714


>> No.65969726

C++ first semester in my uni, and I'm in a third-world shithole.

>> No.65970032

>A C++ vector on the other hand, is a data structure that needs far more data when you create one typed char with 100 members. There is overhead in creating the vector, storing it, and resizing it. It is far easier (and often times more reliable), but you've added quite a bit of code, and that adds time and memory.
What the fuck are you on about. Most of the "code" involved in a std::vector<> implementation is template metaprogramming so it works with any possible type. The actual generated instructions are far less, and post-constexpr can even be zero-overhead in size & time. A vector shouldn't be any bigger or slower than doing the same thing in C. A C++ vector is not the equivalent of a C/C++ array aka int[], that would be a std::array.

>> No.65970166

its fine I have 32 gb

>> No.65970311

>can only sieve up to 32 billion

>> No.65970339

>write a vector implementation in C
>benchmark it
>same exact performance as C++ vectors in all cases but one
>it's much faster than C++ for growing small arrays when a realloc succeeds
>find out C++ "can't" use realloc or any equivalent because of new/delete shenanigans

>> No.65970781

Which third world country? SudAfrikant checking in and can confirm we did C++ in first semester EE

>> No.65970941

Portugal. ECE, C taught in the first year.

>> No.65971245

You can use vectors in C.
I have written a simple macro that allows you to create vectors of a generic type.
It has simple functions like reserving memory in advance pushing back and inserting elements.
it works kinda like this
MAKE_VECTOR(double) //you can use any type
vector_double v;
vector_double_push_back(&v, 13);
int index = 1;
printf("%lf", vector_double_get(&v, index));

Using a macro is better than passing around void pointers because it allows for better optimisation.

>> No.65971265

which explains the post

>> No.65971277


you can do it many ways

>> No.65971284

How fast is that compared to std::vector?

>> No.65971290


for instance, you might implement a linked list...that is basically how c++ implements vectors

>> No.65971293

same goes for stack, queue, and other stl structures. you have to determine the primary data type. c++ allows for templates, enabling generic programming

>> No.65971376

I haven't benchmarked it but it does what you would do by hand in C. The macroed function returning an element from the vector is as simple as
static inline type vector_##type##_get(const vector_##type *vec, size_t index){\ return vec->data[index];\ }
[code]pushing back reallocates twice the memory it is already allocated each time the reserved memory is reached. I have heard std::vector does the same.
It also has a version of push back that does not check if the pushed element is exceeding the reserved memory so you can reserve memory in advance and push elements back as fast as possible.

static inline void vector_##type##_fpush_back(vector_##type *vec, type elem){\ vec->data[vec->size++] = elem;\ }

static inline void vector_##type##_push_back(vector_##type *vec, type elem){\ if (vec->size >= vec->capacity){\ vec->data = realloc(vec->data, sizeof(type)*vec->capacity*2);\ vec->capacity *= 2;\ }\ vec->data[vec->size] = elem;\ vec->size ++;\ }\

As you can see the code is really simple and it does not check for errors in allocation. It just assumes that everything just goes right. It's just a simple experiment i wrote and it's obviously not meant for any serious usage so comparing it to std:: vector does not seem fair.[/code]

>> No.65971390

sorry I fucked up my formatting

>> No.65971402


>C is rarely taught these days
Funny, because I just got done with a networking class that uses C for the assignments.

>> No.65971517

Macro abuse.

>> No.65971528

>What C++ offers over C in this area is restricting access patterns (no private in C),
You can use an opaque handle but that's usually suboptimal in efficiency.

>> No.65971536

static inline
Enjoy your bloated executables.

>> No.65971543

Actually I recently completed my generic vector implementation in plain C
It's basically a heap allocated array of void pointers
I have created some function to move variables in and out of the heap and destroy them as needed so I can easily store in the vector objects of any type or even complex data structures
During initialization I specify the base size.
Once the array fill it automatically allocates more memory with realloc()
Once I delete enough element I can call a trim() function to deallocate unneeded memory
It works very good, it's fast, there are no leaks and it offers nice and fast random access
It's an opaque pointer too, I made so I can't look inside it and just my custom accessor functions to manipulate it (for exaple, sort(), filter(), reverse(), set(), get(), binsearch(), etc)

In other words C can do everything and it's great

>> No.65971550

>It's basically a heap allocated array of void pointers
Sounds inefficient as fuck

>> No.65971558

The functions are rarely longer than a few lines and most of them translate to a very few CPU instructions. There is no need to call a function when all the function does is return a value from memory. It would be inlined by the compiler anyways.

>> No.65971562

I know for a fact that my school uses C for Comp Org 2 and Operating Systems, not to mention the fact that we're a C++ school in the first place.

>> No.65971588

It isn't though
In some basic, not very thorough, tests I did, it's very fast
Rarely you want to use a structure to store a simple data type like an int and I like the flexibility void pointers provide
By passing function pointers to custom destructors, comparators, etc I can easily store complex data types (or even structures containing functions) inside it and repurpose it for any use and the memory management is easy (I just pass a custom destructor once and it handles everything and there are no leaks)
I just need to include a single file and no recompilations are needed, I prefer it than mucking with the preprocessor and abusing it

>> No.65971627


My favourite implementation of vector-like behaviour in C for when I just want something done quick and easy.

>> No.65971729

This seems useful.
I really should take a more thorough look at the stb libraries.

>> No.65971819

>fuck, memory leak

>> No.65972171


>> No.65972266

You're correct when the data structure is a vector but for anything more complicated static inline is gonna bite you in the ass. There's a reason the semantics of inline are different in C++.

>> No.65972697

>t. Rajeesh

>> No.65972766

Which uni?

>> No.65972916

His point, that std::vector and standard c array have a different purpose is still valid. high performance computing often relies on a certain data format, e.g. for sparse matrices. You won't do that with a vector. You need to exactly know what's going on and therefore you use a c array

>> No.65972975

>You need to know exactly how shit your code is because you're a retard who thinks abstraction is bad

That's literally you.

>> No.65973159

At my suny school C is the first language you learn, then c++, then java, and if you're EE/CE you'll be doing lots of assembly and embedded c

>> No.65973735

But it's harder to do sparse matrices in C than in C++. You're not going to be using raw arrays, std::vector, or std::array as the primary storage of a (general) sparse array anyways, because all three are contiguous containers.

>> No.65974584

lel we learn this shit in high school

>> No.65974668

fukken barrett strikes again

>> No.65974698


>> No.65974740

int *test = load_xarray(0, sizeof *test);

test = xarray_expand(test);
test[0] = 3;
test = xarray_expand(test);
test[1] = 5;

printf("test vector size is %d\n", xarray_size(test));

xarray_resize(test, 50);
memset(test+2, 0, 48);


i.e. Opaque AND used like a normal array. (Details are stored before front of the array).

>> No.65974773

Also I'm not actually storing the element size because this is unnecessary, it can be understood from the type of the array (like in std::vector, actually).

>> No.65975192
File: 20 KB, 400x270, 1512772574286.jpg [View same] [iqdb] [saucenao] [google] [report]

I inline everything.

>> No.65975559

enjoy your i$ misses

>> No.65975622

Literally every (good) uni teaches C

>> No.65975657

I use this kind of stuff.
It's so much better than the macro/void* style.

>> No.65976096

This can cause alignment errors.

>> No.65976114

also see

This one works

>> No.65976192

if you don't know when to inline your functions you should honestly just go back to web development lol

>> No.65976599

If you don't know why static inline is a problem for functions longer than a line so should you.

>> No.65976751

>How are vectors written in C? Is it even done? I have a hard time believing developers are satisfied with linear access lists and size constrained arrays.
all this C++ shit worck with speed of BASIC
so why you lose time for C++? just use BASIC, or Python

>> No.65976765


>> No.65976855

dumb nigger, templates are just as efficient as manual implementations

>> No.65976882

the same "manual implementations" build in BASIC and Python and have the same speed like in C++

>> No.65977531

>inline your functions
>they think using the "inline" keyword changes functions into basically macros

>> No.65977555

You can't blame them for not knowing what inline does, because it isn't what it says it does and it's different in C and C++.

>> No.65977595

This video was very hard to watch because I'd previously watched some of Casey Muratori's C++ talks and thought they were generally solid

>> No.65977625

Lmaoing at your life, learned C and C++ in first year of electrical engineering in the US

>> No.65977781

>size constrained arrays
Clearly can't into dynamic arrays.
Another concept that is beyond comprehension of the Pajeet.

>> No.65977823

vectors in c can only take integers? into the trash it goes

>> No.65977848
File: 69 KB, 645x729, 1514091406281.png [View same] [iqdb] [saucenao] [google] [report]


>> No.65979454


what are structs ?
what is *alloc() ?

also, this


>> No.65979483


Learned C first and second semester at uni.
Standard procedure for almost every STEM related degree, certainly CS/CE/EE.

Is this the prime american education i've been hearing so much about ?

>> No.65980139
File: 32 KB, 525x525, 11250167_962594637109981_403696671_n.jpg [View same] [iqdb] [saucenao] [google] [report]


Name (leave empty)
Comment (leave empty)
Password [?]Password used for file deletion.