Quantcast
[ 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

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

>> No.65967896

realloc

>> No.65967951

>>65967896
Ellaborate yourself

>> No.65967971

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

>> No.65968001

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

>> No.65968019

>>65968001
A state university

>> No.65968038

>>65968019
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

>>65968038
Rutgers

>> No.65968085

Are Python list arrays vectors under the hood?

>> No.65968177

>>65967827
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

>>65968085
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.
https://github.com/python/cpython/blob/master/Objects/listobject.c

>> No.65968214

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

source: pure guess

>> No.65968283

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

>> No.65968287

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

>> No.65968302 [DELETED] 

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

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

>> No.65968305

>>65968287
Proof?

>> No.65968315

Same way it is written in C++.

>> No.65968326

>>65968305
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

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

>> No.65968343

>>65968302
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?
>>65968315
Idk about that, C doesn't have methods.

>> No.65968351

>>65968343
Meant to reply to
>>65968341

>> No.65968365

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

>> No.65968373

>>65968343
realloc

>> No.65968374

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

>> No.65968381

>>65968343
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

vector_delete(v);

>> No.65968398

>>65968381
>on the heap

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

>>65968381
THAT DOESN'T COUNT

>> No.65968425

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

>> No.65968427

>>65968283
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

>>65968381
vector v;
vector_new(&v)

vector_push_back(&v, 5);

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

vector_delete(&v);

>> No.65968444

>>65967827
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

>>65968436
meant for >>65968398

>> No.65968474

>>65968085
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

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

>> No.65968617

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

>> No.65968645

>>65967852
What kind of shitty uni doesn't teach C?

>> No.65968651

Reminder:

Linked lists are terrible for caching

:-)

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

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

>> No.65968700

>>65968651
don't modern processors all have markov cache predictors?

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

>>65968651

>> No.65968759

>>65968085
They are extensible arrays iirc.

>> No.65968778

>>65968757
> he doesn't use unrolled linked lists

>> No.65968917

>>65968645
checking in

>> No.65968945

>>65968474
>op
>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

>>65968945
> he doesn't know about unrolled linked lists
S I G H

>> No.65968983

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

>> No.65969030

>>65968945
>he doesnt utilize every single bit

>> No.65969055

>>65968980
Not applicable to Python.
>>65968983
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

>>65967827
>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]
65969153

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

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

>> No.65969186

>>65967971
at my uni the first year is almost entirely Scheme.

>> No.65969236

>>65969153
good now rewrite it in C

>> No.65969237

>>65969186
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]
65969264

>>65969236
>he thinks I know C

>> No.65969274

>>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?
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

>>65968444
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

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

?

>> No.65969353

>>65969264
>he cant write a basic C program

>> No.65969416

>>65967827
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]);
free_xarray(test);

>> No.65969563

>>65967852
This board is for Americans, friend.

>> No.65969586

>>65968214
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]
65969690

>vector
>it's actually an array

>> No.65969714

>>65969690
????????

>> No.65969726

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

>> No.65970032

>>65968177
>>65968427
>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

>>65968945
its fine I have 32 gb

>> No.65970311

>>65970166
>can only sieve up to 32 billion

>> No.65970339

>>65967827
>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

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

>> No.65970941

>>65967852
Portugal. ECE, C taught in the first year.

>> No.65971245

>>65967827
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_construct(&v);
vector_double_push_back(&v, 13);
int index = 1;
printf("%lf", vector_double_get(&v, index));
vector_double_free(&v);

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

>> No.65971265

>>65969563
which explains the post

>> No.65971277

>>65967827

you can do it many ways

>> No.65971284

>>65971245
How fast is that compared to std::vector?

>> No.65971290

>>65967827

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

>> No.65971293

>>65967827
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

>>65971284
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

>>65971376
sorry I fucked up my formatting

>> No.65971402

>>65967852

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

>> No.65971517

>>65967827
Macro abuse.

>> No.65971528

>>65969148
>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

>>65971376
static inline
Enjoy your bloated executables.

>> No.65971543

>>65967827
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

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

>> No.65971558

>>65971536
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

>>65967852
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

>>65971550
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

https://github.com/nothings/stb/blob/master/stretchy_buffer.h

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

>> No.65971729

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

>> No.65971819

>>65967852
>fuck, memory leak

>> No.65972171

>>65971627
this

>> No.65972266

>>65971558
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

>>65967852
>t. Rajeesh

>> No.65972766

>>65970941
Which uni?

>> No.65972916

>>65970032
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

>>65972916
>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

>>65968038
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

>>65972916
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

>>65967852
lel we learn this shit in high school

>> No.65974668

>>65971627
fukken barrett strikes again

>> No.65974698

>>65971245
>>65971284
>>65971376
>>65971536
>>65971558
>>65972266
see
>>65969416

>> No.65974740

>>65974698
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);

free_xarray(test);


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

>> No.65974773

>>65974740
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]
65975192

>>65971536
I inline everything.

>> No.65975559

>>65975192
enjoy your i$ misses

>> No.65975622

>>65967852
Literally every (good) uni teaches C

>> No.65975657

I use this kind of stuff.
https://github.com/nothings/stb/blob/master/stretchy_buffer.h
It's so much better than the macro/void* style.

>> No.65976096

>>65971627
>>65971729
>>65972171
This can cause alignment errors.

>> No.65976114

>>65975657
also see
>>65976096

This one works
>>65969416

>> No.65976192

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

>> No.65976599

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

>> No.65976751

>>65967827
>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

>>65967852
lolwat

>> No.65976855

>>65976751
dumb nigger, templates are just as efficient as manual implementations

>> No.65976882

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

>> No.65977531

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

>> No.65977555

>>65977531
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

>>65977555
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
https://www.youtube.com/watch?v=B2BFbs0DJzw&

>> No.65977625

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

>> No.65977781

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

>> No.65977823

>>65968381
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]
65977848

>>65977823

>> No.65979454

>>65967827

what are structs ?
what is *alloc() ?

also, this

>>65967834

>> No.65979483

>>65967852

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]
65980139

>>65967852

>>
Name (leave empty)
Comment (leave empty)
Name
E-mail
Subject
Comment
Password [?]Password used for file deletion.
Captcha
Action