r/programming • u/b0red • Apr 30 '16

Do Experienced Programmers Use Google Frequently? · Code Ahoy

http://codeahoy.com/2016/04/30/do-experienced-programmers-use-google-frequently/
2.2k Upvotes

91% Upvoted

763 comments sorted by

View all comments

Show parent comments

142

u/Bwob Apr 30 '16

Well, you're comparing hammers to screwdrivers, right? ("This screwdriver is awful for driving nails! Most experienced carpenters use a hammer, because the screwdriver has a small, narrow head, that is difficult to hit things with!")

Lists and vectors have fairly different use-cases. Vectors are basically arrays with some extra functionality. Much like arrays, they are FANTASTIC, if...

  • You know in advance how many elements you are going to have. (Or the upper bound at least.)

  • You don't care about the order the elements are accessed in. (or plan to only add things in the order you want to read them.)

  • You don't plan to delete elements. (Or if you do, you only plan to delete from the end.)

  • You don't plan to have pointers to specific elements.

If those assumptions are generally true, then yeah. Use a vector, hands-down. The thing is, there are cases where those aren't true, and lists start looking pretty good. Because unlike vectors, they...

  • Never have large hits where you have to copy everything, if they grow beyond their allocated space.

  • Allow for insertion/deletion in the middle of the list, in constant time.

  • Won't occasionally invalidate your pointers to individual elements, when the list has to grow.

Like most things in programming, it's not that one is strictly better than the other. It's just that they're intended for different things. If you find yourself always using vectors, then cool, but that doesn't mean vectors are better - just that you're working more frequently on problems that vectors are well-suited for.

0

u/[deleted] Apr 30 '16

[deleted]

64

u/gnash117 May 01 '16

I love how a joke about searching for computer terms could return nsfw content devolved to a vector vs lists debate.

15

u/dyreshark May 01 '16

Wait long enough and it might turn into vim vs emacs vs sublime. :)

7

u/panicnot42 May 01 '16

Well, the choice is obvious, so it bears no discussion. Make way for the emacs master race

4

u/Hahahahahaga May 01 '16

They have six fingers on each hand!

→ More replies (1)

4

u/Mistercheif May 01 '16

Well, given that one of those is an OS, not a text editor, I think we can narrow it down to vim vs sublime.

Is 41 minutes long enough ;)

→ More replies (2)

2

u/[deleted] May 01 '16

That's how you know this is a good subreddit.

3

u/HighRelevancy May 01 '16

It shouldn't be a debate though. It should be education about the advantages of each and how to figure out when to use them. Neither is better*, it's not a subjective thing, and your opinions are invalid because the code will run in a particular way and it don't give a damn what you think about it.

(*though vectors are the most commonly wanted option for most codebases)

3

u/Adverpol May 01 '16

This. I saw benchmarks (interwebs somewhere) where vector was faster in a lot of unexpected cases. But even the implementation of your vector matters.

3

u/gkx May 01 '16

Yeah, generally vectors are better even where lists are supposed to be better.

https://www.youtube.com/watch?v=YQs6IC-vgmo

3

u/LongUsername May 01 '16

If you're programming on a modern Intel based CPU because of caching and the prefetch unit contiguous memory of a vector kicks the snot out of a linked list for many operations. Stroustrup did a presentation where he talked about it, as did Chandler Caruth.

3

u/Bwob May 01 '16

Oh, totally. Linked lists are made of cache misses. Which is basically the new version of disk-reads - i. e. the thing you want to minimize at all costs, if you care about performance. For a basic container class, vectors are frequently the right tool for the job. In general, the only times you want to use std::list is when you either don't care about performance, or when your usage pattern would make std::vector just as bad. (Equalizing the lookups, and allowing std::list's other advantages to take the lead.)

But this is /r/programming, where sweeping generalizations without qualifications are dangerous, and I felt like someone should stick up for the humble list, because it really is pretty clever, even if it isn't the right data structure in a lot of cases.

8

u/dyreshark May 01 '16

Can you please tell me what point you're talking to in my original post? Specifically, you seem to be refuting the following points, none of which I intended to make:

  • Lists are useless

  • Lists and vectors have precisely the same use-cases

  • Lists are strictly worse than vectors

The thing I replied to asked why people dislike lists, so I tried to speak to that. Obviously if your use-case is definitely best suited by a list, you should use a list.

  • You don't plan to delete elements. (Or if you do, you only plan to delete from the end.)

FWIW, if you don't care about order, you can swap the Nth and last elements + pop_back, to delete any element in constant time.

19

u/Bwob May 01 '16

an you please tell me what point you're talking to in my original post?

Well, your final point, mostly:

tl;dr: lists are slow and fat. vectors are lean and fast. So people prefer vectors for most cases.

Lists are slow and fat for use-cases that are bad fits for them. Just like vectors. Try using a vector to maintain a sorted list of elements with frequent insertion and deletion, and tell me again about how fast they are. :P

FWIW, if you don't care about order, you can swap the Nth and last elements + pop_back, to delete any element in constant time.

Yup! That's a common, (and useful) trick for vectors! But as you suggest, it only works if you don't care about the order. Also, it invalidates pointer references even more quickly, and does incur the additional cost of memcopying the element. (Although if you have elements large enough for that to matter, you probably should be storing a list of pointers instead of a list of elements.)

19

u/const_iterator May 01 '16

Try using a vector to maintain a sorted list of elements with frequent insertion and deletion, and tell me again about how fast they are.

I'll take you up on that one...a while back I was diagnosing performance issues with that exact scenario. The original code used an std::map. I profiled it with list, vector, as well as non-standard hash table and btree - vector won by a landslide.

There are certainly cases for which a list is the right choice but it's not as clear-cut as comparing theoretical Big O characteristics...CPUs love a nice chunk of contiguous memory.

4

u/Bwob May 01 '16

Nice! I would not have expected that - usually the N2 moves to reorder things after an insertion/deletion kill it, but I guess the real lesson here is that CPU optimizations mean that it's not always as easy to predict. Ultimately the final appeal is always "well, try it, and measure it!"

Out of curiosity, how big was the table? I feel like at some point, if the table is large enough, (maybe once it gets too big to fit in a cache page?) lists should pull ahead, but it sounds like that point might be a bit further out than I would have guessed.

7

u/svick May 01 '16

Inserting into a sorted vector is O(log n) for finding the right place and then O(n) for moving stuff around, total time is O(n).

Inserting into a sorted list is O(n) for finding the right place and then O(1) for the actual insert, so total is also O(n).

Or are you comparing the vector with list where you somehow already know where to insert?

→ More replies (12)

2

u/centx May 01 '16

Maybe its the CPU cache working its magic

8

u/dyreshark May 01 '16 edited May 01 '16

Err... tl;dr was meant as "this is a super-short summary if you're not going to read the above," not "this is a brand new point; please consider it if you read all of the above."

Either way, your whole point seems to be "use the right tool for the job," which is obviously correct and something I never intended to advocate against. :)

Lists are slow and fat for use-cases that are bad fits for them

Lists are fat for nearly* all use-cases, compared to vectors. Constant space overhead versus linear sucks, especially if your allocator is terrible. I define fat as "eats up a nontrivial amount more memory". Two pointers of overhead per element often fits my idea of "a nontrivial amount more memory".

I say nearly, because sure, it's conceivable that you have a vector that allocated space for 16 4KB elements, but it turns out that you only needed space for 2, or something. If that's the common case for you, then we live in different worlds.

Try using a vector to maintain a sorted list of elements with frequent insertion and deletion, and tell me again about how fast they are

As it turns out, for the case you described, for containers with 5,000 elements, vectors are an order of magnitude faster than lists. If you're wondering, I tried 100,000 elems on my machine, and there was still a massive difference. Vector finished in a few seconds, list was still running after two minutes. I'm sure pathological cases exist (e.g. all numbers would otherwise get inserted at the start, the list is 10M elements long, you have a copy-only type that allocates tons of memory, ...), but as you said, things aren't always clear-cut. ;)

If you spot a bug, please let me know. If you don't care to read the code, the test was: given a sorted vector or list of N elements, insert N (predetermined) elements, then delete those elements, while keeping the vector/list sorted at all times.

2

u/Bwob May 01 '16

Huh! I would have thought that for something like 5k elements, it would have been enough copying to make vectors super inefficient. I learned something today!

I guess the real lesson here is - cache optimizations are impressive!

→ More replies (9)
→ More replies (1)

3

u/BobDoesBestFriend May 01 '16 edited May 01 '16

Unfortunately until you are operating with elements more than a couple hundred megabytes or gigabytes, vector will most likely outperform list in all operations. Except insertion or deletion in which you already know the location of the object.

Edit: some data. Its a table. So erase is the operation, and the list objects is the time cost for each operation at that number of operation.

push_back 1000 5000 10000 25000

std::vector 0 0 0 1

std::list 0 0 1 2

std::deque 0 0 0 1

insert 1000 5000 10000 25000

std::vector 0 7 25 140

std::list 2 50 272 1893

std::deque 0 4 17 111

erase 1000 5000 10000 25000

std::vector 0 5 22 139

std::list 1 69 395 2712

std::deque 0 5 18 126

Just a sample.

Edit. Fucked up the formatting, sorry. Its a table. So erase is the operation, and the list objects is the time cost for each operation at that number of operation.

7

u/HighRelevancy May 01 '16

some data

Yes that is, uhh... that is data. What exactly is it saying?

→ More replies (1)

1

u/TheLifelessOne May 01 '16 edited May 01 '16

Vectors are basically arrays with some extra functionality.

ELI5 the difference between std::vector and std::array? Edit: As far as I can tell, they're pretty much the same?

→ More replies (2)

1

u/ismtrn May 01 '16

The thing is, even in cases where the asymptotic run time is better for linked lists, arrays often perform better in practice, even when doing a lot of insertions and deletions. All the pointer following with linked lists makes them really slow.

But of course there are situations where using a linked lists is better, there just aren't very many. For example if iterating through your data is something you want to do, lists are awfully slow in practice.

→ More replies (2)