(Part 2) Reddit mentions: The best algorithms and data structures books

> Mathematical Logic

It's not exactly Math Logic, just a bunch of techniques mathematicians use. Math Logic is an actual area of study. Similarly, actual Set Theory and Proof Theory are different from the small set of techniques that most mathematicians use.

Also, looks like you have chosen mostly old, but very popular books. While studying out of these books, keep looking for other books. Just because the book was once popular at a school, doesn't mean it is appropriate for your situation. Every year there are new (and quite frankly) pedagogically better books published. Look through them.

Here's how you find newer books. Go to Amazon. In the search field, choose "Books" and enter whatever term that interests you. Say, "mathematical proofs". Amazon will come up with a bunch of books. First, sort by relevance. That will give you an idea of what's currently popular. Check every single one of them. You'll find hidden jewels no one talks about. Then sort by publication date. That way you'll find newer books - some that haven't even been published yet. If you change the search term even slightly Amazon will come up with completely different batch of books. Also, search for books on Springer, Cambridge Press, MIT Press, MAA and the like. They usually house really cool new titles. Here are a couple of upcoming titles that might be of interest to you: An Illustrative Introduction to Modern Analysis by Katzourakis/Varvarouka, Understanding Topology by Shaun Ault. I bet these books will be far more pedagogically sound as compared to the dry-ass, boring compendium of facts like the books by Rudin.

If you want to learn how to do routine proofs, there are about one million titles out there. Also, note books titled Discrete Math are the best for learning how to do proofs. You get to learn techniques that are not covered in, say, How to Prove It by Velleman. My favorites are the books by Susanna Epp, Edward Scheinerman and Ralph Grimaldi. Also, note a lot of intro to proofs books cover much more than the bare minimum of How to Prove It by Velleman. For example, Math Proofs by Chartrand et al has sections about doing Analysis, Group Theory, Topology, Number Theory proofs. A lot of proof books do not cover proofs from Analysis, so lately a glut of new books that cover that area hit the market. For example, Intro to Proof Through Real Analysis by Madden/Aubrey, Analysis Lifesaver by Grinberg(Some of the reviewers are complaining that this book doesn't have enough material which is ridiculous because this book tackles some ugly topological stuff like compactness in the most general way head-on as opposed to most into Real Analysis books that simply shy away from it), Writing Proofs in Analysis by Kane, How to Think About Analysis by Alcock etc.

Here is a list of extremely gentle titles: Discovering Group Theory by Barnard/Neil, A Friendly Introduction to Group Theory by Nash, Abstract Algebra: A Student-Friendly Approach by the Dos Reis, Elementary Number Theory by Koshy, Undergraduate Topology: A Working Textbook by McClusckey/McMaster, Linear Algebra: Step by Step by Singh (This one is every bit as good as Axler, just a bit less pretentious, contains more examples and much more accessible), Analysis: With an Introduction to Proof by Lay, Vector Calculus, Linear Algebra, and Differential Forms by Hubbard & Hubbard, etc

This only scratches the surface of what's out there. For example, there are books dedicated to doing proofs in Computer Science(for example, Fundamental Proof Methods in Computer Science by Arkoudas/Musser, Practical Analysis of Algorithms by Vrajitorou/Knight, Probability and Computing by Mizenmacher/Upfal), Category Theory etc. The point is to keep looking. There's always something better just around the corner. You don't have to confine yourself to books someone(some people) declared the "it" book at some point in time.

Last, but not least, if you are poor, peruse Libgen.

I worked through the following books:

The C Programming Language (the one you mentioned).
It's a classic for a reason! It might not be completely up to date (which is a common complaint), but once you work through this book becoming up to date doesn't require much effort. You learn a lot about the core C language with this book, which is very helpful. Lots of challenging exercises (make sure to do as many as you can!)

Data Structures in C - Kalicharan

I really like this one because it's absolutely packed with exercises, it's also very short (300-ish pages) and it takes a much more practical approach to learning about data structures and some basic algorithms using C. I wouldn't pay too much attention to the 3.5 review - one guy gave it a 1-star because of the font (okay, the font is a little cartoony I guess, but that's not worth dropping the whole book down to 1) and another complains about the book being sold under a newer edition with the same ISBN, which is a bit whacky I guess, but again, doesn't really talk about the content of the book itself. It has loads of code and a shitload of exercises to help reinforce knowledge.

Finally, I really liked Understanding and Using C Pointers - Reese.

This is another great short/concise book (~220 pages) and it will really help to iron out any mental rough spots you might have in regards to pointers. 'The C Programming Language' does go into pointers, but this tiny book really helped completely flesh them out for me and went into more advanced scenarios.

With the above books I really felt like I got a very thorough education in C and the great thing was none of them bog you down in academia, they are all very short and practical for every day developers.

I think a lot of people confuse programming with programming languages. I see a lot of people say things like "I learned <insert programming language here> but I still have no idea what I'm doing."

This is because programming is more than just the language you use. It is a set of skills, including mastery of a language, algorithms, data structures, design principals (and patterns), hardware knowledge, math, logic, problem solving... the list could go on.

Mastering a language is just one part of the equation. Depending on the kind of programs you want to create, you will have to master some, all, or more of the other skills I've mentioned.

I would start with data structures and algorithms. Since a lot of programming has to do with data, it's good to know the various ways it can stored, sorted and manipulated. You probably already know about simple data structures, like arrays, but there are many more, like lists, trees and maps. Algorithms like sorting, searching and pattern matching will help you solve some very common problems you'll encounter. Either enroll in a course on data structures and algorithms (they're generally taught together) or find yourself a good book.

Once you've mastered that, move on to design. Learning how to design a large program is an art and a science unto itself. There are many useful design patterns that, once you know how they work, you can apply directly to your own designs. While they're not the end-all-be-all of computer program design, they're proven effective and can be extremely useful.

Another thing you should definitely understand is how computers work. Now I"m sure you have a general idea of how a processor and memory works, but do you really understand the underlying architecture? Do you know how registers work? How instructions are stored? How the operating system interfaces with the various hardware? How the software interfaces with the operating system? While this knowledge isn't 100% necessary, it can be very helpful to understand how your programs are functioning on a low level. Most modern languages abstract most of that out, but keeping it in the back of your mind can only help.

Anyhow, I know how you feel, and don't worry too much about it. Programming is a life long learning endeavor. There will always be new things to learn, new ways to do things, and new technologies to understand, but if you stick with it, you'll eventually learn it.

Just think, every piece of software in the world was written by someone who, at one time or another, knew absolutely nothing about programming.

I started getting interested in C# after PHP, and I absolutely love it now!

If you google for "C# tutorial" you'll find articles which take it form the very beginning. Only make sure they're recently written.

If you want books, you can check out C# 4.0 The Complete Reference and C# 4.0 in a Nutshell: The Definitive Reference. There is also a free language specification available from Microsoft: C# Language Specification 4.0.

Considering that you're a network engineer, you might want to use C# for solving network-related stuff. There's a book for that, C# Network Programming (although, it might be a little bit old.)

When you start developing in Visual Studio 2010, make sure you also install the ReSharper extenion, which can be very helpful even for a seasoned developer.

A free edition of Visual Studio is available under the name of Visual C# 2010 Express Edition. If you want Microsoft Visual Studio 2010 Ultimate version, a 60-day trial is downloadable. Alternatively, you can get the free and open-source .NET IDE SharpDevelop.

I hope you'll love the language as much as I do. :)

Sorry, got busy for the holidays.

It seems like you're falling victim to the same cycle that a lot of us have. You can't get a job without experience, but you can't get experience without a job. It doesn't make a ton of sense.

Google/Amazon/Uber rely heavily on data structure and algorithm knowledge in their interviews. I have the first edition of this book for JS data structures. I went through it and coded all of them out. It helps to understand them.

In my master's program, I had a class on algorithm design that in hindsight, I wish I had paid more attention to. We used this book but I think there are better ones available now.

I have this book as a general interview reference which may summarize the above two suggestions better for the interviews.

Time/space complexity was also helpful information to know. Big O notation is a useful thing to have in your arsenal to begin with.

These are just suggestions for notorious interviews for infamous tech companies. Not every company is going to grill you about these concepts. But having been someone who has failed several intense programming interviews, and now conducts them for our company, I think all of this information is applicable, and a true tech company likely won't grill you about job experience if you can apply these concepts on a whiteboard without thinking about it.

Data Science is a great spot to be in right now. Spend a little time every day applying some programming principles to big datasets. It should be enough to land you a job at a solid company if even at an entry-level position.

Also, get out of AngularJS and learn Angular 2+. React/React Native also seem to be in high demand. They have become commonplace at most large companies trying to stay on the edge of technology for their users.

For compsci you need to study tons and tons and tons of discrete math. That means you don't need much of analysis business(too continuous). Instead you want to study combinatorics, graph theory, number theory, abstract algebra and the like.

Intro to math language(several of several million existing books on the topic). You want to study several books because what's overlooked by one author will be covered by another:

Discrete Mathematics with Applications by Susanna Epp

Mathematical Proofs: A Transition to Advanced Mathematics by Gary Chartrand, Albert D. Polimeni, Ping Zhang

Learning to Reason: An Introduction to Logic, Sets, and Relations by Nancy Rodgers

Numbers and Proofs by Allenby

Mathematics: A Discrete Introduction by Edward Scheinerman

How to Prove It: A Structured Approach by Daniel Velleman

Theorems, Corollaries, Lemmas, and Methods of Proof by Richard Rossi

Some special topics(elementary treatment):

Rings, Fields and Groups: An Introduction to Abstract Algebra by R. B. J. T. Allenby

A Friendly Introduction to Number Theory Joseph Silverman

Elements of Number Theory by John Stillwell

A Primer in Combinatorics by Kheyfits

Counting by Khee Meng Koh

Combinatorics: A Guided Tour by David Mazur


Just a nice bunch of related books great to have read:

generatingfunctionology by Herbert Wilf

The Concrete Tetrahedron: Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates by by Manuel Kauers, Peter Paule

A = B by Marko Petkovsek, Herbert S Wilf, Doron Zeilberger

If you wanna do graphics stuff, you wanna do some applied Linear Algebra:

Linear Algebra by Allenby

Linear Algebra Through Geometry by Thomas Banchoff, John Wermer

Linear Algebra by Richard Bronson, Gabriel B. Costa, John T. Saccoman

Best of Luck.

This is not a good approach to garbage collection, but it's the best you can do, sans optimization, for a language like C. It's not unsafe if done correctly since you err on the side of caution and assume anything that could be a pointer is a pointer. It is quite slow and will leak some memory over time (due to misclassifying integers as pointers), which is why languages that are designed for garbage collection use more efficient designs requiring cooperation from the language.

If you're interested in the stuff, I highly recommend The Garbage Collection Handbook. It's loaded with information and algorithms but also includes approachable, pragmatic discussion of the characteristics and tradeoffs of automatic memory management systems.

I came here to put this same book. This book is crazy, crazy good. It would help to have some knowledge of algorithms and data structures before going in as the examples aren't vast and the information are fairly heavy, but it's a fantastic reference.

I would encourage you to change your thinking from "learning algorithms in Ruby" to "learning algorithms" and then just implementing examples in Ruby. There are a few classic Algorithms book that I'd highly recommend. In addition to The Algorithm Design Manual, Data Structures in C is written in C but fairly generic and gives you the right tools for thinking about performance and algorithms, and Introduction to Algorithms, 3ed is more academic but also stupid inexpensive right now. It's a great learning book as the examples are very detailed. It's aimed at interviewing but Cracking the Coding Interview has a nice short survey of algorithms and data structures too

The books posted are great for 3D rendering.

However, you're a flash developer and I'm concerned about your proficiency level with C++. If you're meh at C++, then I recommend that you write some sample C++ code to get the hang of C++ before you dive into implementing 3d mathematics and rendering.

Some resources for C++:
http://www.amazon.com/C-Pointers-Dynamic-Memory-Management/dp/0471049980

Although the best way to get good at C++ is to just code in C++! :)

Also you need a strong foundation in 3D math before getting to the rendering:
http://www.amazon.com/Primer-Graphics-Development-Wordware-Library/dp/1556229119

I agree to some degree. WIth java you're limited, you cant use pointers, and it has some limiting factors. However, trying to teach pointers to new freshmen who've never pulled the side off their computers would probably drive more off than already leave (and CS has a large enough group that leave that our intro class actually teaches every student where they need to go to change their major). By not requiring you to do memory management or any of the complex stuff though it makes java a lot easier to learn on. You learn the more complex stuff in the C and C++ classes.

Whether the teacher will let you use any language for the course is up to them. I've had teachers say sure (like my 356 teacher) and other teachers say no. It makes the grading harder when you have 35 programs written in a variety of languages, which is why they usually limit the languages you can use. I've had a couple friends get around that by making one program run a program in a different language, but that was more just as a middle finger to the teacher because they wouldn't let them use the other language in the first place.

I've heard fantastic things about compilers. Wim (one of the teachers) is a great guy, a fantastic teacher and he's really awesome to learn from. His tests are conceptual, they're short, but if you know the material they're really easy, and if you don't they're impossible. Straut (the other possible teacher) i've also heard great things about but never had. I've talked to her a few times and she seems nice, but i've heard she's quite a bit harder, which can be good or bad depending on whether you're looking to slide through or looking for a challenge and to learn.

We only require up to Calc1, Calc 2 and either Math 229 or Math 361 (I think that's the number). From what I understand Calc at CSU sucks. It's taught by TAs and is generally no fun to take, so take it at front range or somewhere else and transfer in credit. That's what I did.

I personally hate Math 229, it's also taught by TAs so the quality of the class is inconsistent, but the book is absolutely horrible. It was written by a math prof here (Who has since died I believe), but the book doesn't explain things, doesn't give good examples and is pretty much the worst textbook i've ever had. Here. Read the amazon reviews. It's not that the material or the class is hard, just read the book before each class (probably several times), and come to class with LOTS of questions about the possible homework problems. I'd like to suggest the other math class instead of 229, but I don't have any experience with it.

The math requirements are probably the suckiest part of the entire CS department's undergrad requirements. We loose a lot of kids because they can't pass calc1 or calc2. They never really get into the Computer part of Computer science because you have to pass all the calc before you get into the 200 levels.

I have no idea how it compares to CU when it comes to languages as i've never taken a class from CU.

Yes there are, in audio we use vectors all the time and we often access them in a lock-free way.


I highly suggest two resources:

https://www.amazon.co.uk/High-Performance-Boost-optimize-performance/dp/1787120953/ref=sr_1_1?ie=UTF8&qid=1540597989&sr=8-1&keywords=high+performance+c%2B%2B

https://www.youtube.com/watch?v=qdrp6k4rcP4


I am actually writing something with Peter Doumler on this exact subject but might as well answer your question now.

Basically making a lock-free data structure is a checklist.

1. Use atomics correctly to avoid data races
   
2. No memory reallocation
   
3. No Locks
   
   You can use atomics on values that are small enough or trivially copyable. Atomics also require hardware support but that is the case for most modern systems. So you can get Atomics for int, bool, and * . This is actually sufficient. Some hardware does allow for atomic float but this is far from normal. So basically if you need atomic access to a float, you must use pointers. If you look at those resources then it will make sense.
   
   So basically you might want to consider making a custom data structure called a ring buffer. This is discussed in both of those resources. A ring buffer is essentially a vector with a read head and write head. The write head obviously writes data to the vector and the read head swaps empty for the value. In other words, that read head will take the value and replace it with nothing. These heads could be indeces but you could make a pointer to a value.
   
   When a ring buffer is made, it is of a fixed size. This size cannot change as that requires memory re-allocation which creates locks. The reader and writer increment through this fixed size buffer and when they get to the end of the vector they loop back around. If the buffer is full, then the read head is one behind the write head. If the buffer is empty, then the read head and the write head point to the same location. This ensures that there are no data races as:
   
   
4. The only time you are accessing the same place in memory is when the vector is empty.
   
5. You are only carrying out one operation on a places in memory at one time.
   
   It is possible to have more than one read head. However, most people just tend to use ring buffers in the way I described.
   
   Hope this helps.
   
   But you may not want to make a ring buffer yourself as there are some available already. Boost has one which was already linked to you.
   
   RingBuffer aka Lock-Free FIFO
   
   ​

I've only used cython a couple times but my experience was fantastic.

In the first case I had a simulator that was spending most of its time calculating distances between points and the nearest lines. I knew my algorithm was good, but profiling showed that the bare arithmetic was enough to make my code unacceptably slow.

Just extracting this function to a .pyx file and setting up the build correctly got me a 5x speedup. Then I added typedefs for the ints and floats and got an additional 10x speedup.

After crowing about this to a colleague she wanted to use cython to speed up a slow loop in some data analysis code. Again we got 5x just for putting the slow part in a .pyx file. There was a little more effort here figuring out how to correctly declare numpy arrays, but after that she also saw a roughly 10x additional speedup.

In both cases there was some necessary upfront work of profiling the code and refactoring to isolate the computationally intensive part. But if this is straightforward, cython can be a very quick win.

I recommend the book High Performance Python

http://www.amazon.com/High-Performance-Python-Performant-Programming/dp/1449361595/ref=sr_1_1?ie=UTF8&qid=1425266485&sr=8-1&keywords=high+performance+python

which taught me a lot about profiling, cython, and other tools for speeding up Python code.

I think that Problem Solving with Algorithms and Data Structures on interactivepython is actually perfect to start with - it gives you a good overview of both the technical concepts and implementations. It's not extremely rigorous, either.

Why not try going through it, and learn whatever you can? It's actually an interactive version of the book Problem Solving with Algorithms and Data Structures by Brad Miller and David Ranum (you can find a copy of the PDF here), which is one of the recommended textbooks of MIT's 6.006 Introduction to Algorithms along with CLRS.

On another note: if you'd like an language-agnostic approach that focuses more on algorithmic thinking, analysis, and some implementation in psuedocode, check out Algorithms: Design and Analysis offered by Stanford on Coursera.

I had a look through Core Techniques and Algorithms in Game Programming at the library, and it's now on my wish list. I haven't read it through yet, but it looks like a really good higher level overview of some things.

Does anyone know any more about this book?

So, (IMO) the raspberry pi doesn't specifically bring anything to learning C++ that I think you couldn't get on any other computer. And I'm assuming you have a computer because you're posting here (could be a phone but i don't know).

If you've got windows I tend towards Visual Studio and on a Mac I'd go with Xcode. When I'm in Linux I tend to just go straight to gcc and make (this won't make sense to you yet)

Books: These are the ones that were used in my C++ focused classes:

Big C++
ADTs, Data Structures and Problem Solving in C++

Hope this helps.

I just recently discovered pythonbooks.org and it looks like a pretty good resource for books on Python, and it has categories for beginner, intermediate, and more specific topics.

Here's pythonbooks.org page on networking.

Here's a link to High Performance Python (chapter on concurrency w/multiprocessing)

If you want more than an overview:

https://www.amazon.com/Garbage-Collection-Handbook-Management-Algorithms/dp/1420082795

Or, if you're on a budget, the previous edition can be had for under $20 used:

https://www.amazon.com/Garbage-Collection-Algorithms-Automatic-Management/dp/0471941484

What can be even cheaper is to pick a recent GC paper (e.g. https://www.cs.utexas.edu/~speedway/fp031-kermany.pdf) and then follow the citations back in time. Often if you google the author and the name of the paper, you'll find a .edu hit on the first page of google that has the paper as a PDF for free (either the author(s) themselves host it, or a professor teaching a class posted it for their students to read).

For basic background, read:

https://en.wikipedia.org/wiki/Cheney's_algorithm

and

https://en.wikipedia.org/wiki/Tracing_garbage_collection#Basic_algorithm

As Cheney's algorithm and tri-color marking are two of the basic building blocks for many other GC algorithms.

Unlike some other topics in CS, garbage-collection papers tend to not invent their own mathematical notations for describing their algorithms, and they tend to be more empirically focused (since worst-case bounds on most novel GC algorithms are not particularly interesting). Those two things make the papers quite approachable.

Here's an open source book on the topic. And also a more computationally focused texted as well.

I've also heard good things about [this one](Combinatorics: Topics, Techniques, Algorithms https://www.amazon.com/dp/0521457610/ref=cm_sw_r_cp_api_iCKzxbCVJHRQ4), [this one ](Combinatorics: A Guided Tour (MAA Textbooks) https://www.amazon.com/dp/0883857626/ref=cm_sw_r_cp_api_ZCKzxb7XY8RJS), and [this one](A Walk through Combinatorics: An Introduction to Enumeration and Graph Theory (Third Edition) https://www.amazon.com/dp/9814460001/ref=cm_sw_r_cp_api_pDKzxbR3CYQGF)

Keep learning it! I thought I knew C++ pretty well. Then I started my data structures class. This book has greatly expanded my understanding of C++. I'm still not even close to done. But I'm working on other languages and learning how compilers work now as well. It never ends muwhahaha

Would recommend The Nature of Code and Processing Handbook for parametric methods. Haven’t seen anything too comprehensive on AI models like GANs yet though.

Can you give more detail about your present background/what sorts of combinatorics you're interested in? If you're new to combinatorics it's hard to do better than Miklos Bona's book.

Have you looked at The Nature of Code? https://www.amazon.com/Nature-Code-Simulating-Natural-Processing/dp/0985930802/ref=sr_1_4?ie=UTF8&qid=1492058474&sr=8-4&keywords=processing


You might find something there to spark your interest.

Hopefully a book that has a high utility but low incidence of suggestion:

Garbage Collection: Algorithms for Automatic Dynamic Memory Management

I had been writing garbage collectors for a year or so before getting this book, and it really changed the way I think about resource allocation on a computer. It's a topic that I don't think is as broadly applicable as some of your other suggestions, yet it's one which turns out to be applicable for a wide variety of problems--it teaches a certain class of patterns that you can use even if you never write a garbage collector.

It’s gonna be hard to give you much without picking a specific OS—details can vary widely even within a single OS family line—but an OS book is probably a good place to start. Tanenbaum’s book is the go-to.

Alternatively, there are books on specific techniques like garbage collection, or books more generally on programming for UNIX/POSIX/Linux or Windows (via Win16/32/64 API, not the six-mile-high shitheap piled atop), which would tell you some about how memory management works in down at least to whatever abstract hardware interface the kernel uses.

Miller and Ranum (https://www.amazon.com/Problem-Solving-Algorithms-Structures-Python/dp/1590280539) was what I used and is fantastic.

Foundations of Data Science by Bloom/Hopcroft/Kannan. It's a free book and updated regularly(this edition here is dated June, 2017). Heavily overlaps with Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis by Mitzenmacher/Upfal.

I can absolutely recommend Algorithms by Johnsonbaugh. Excellent book. Only thing is it's strictly using pseudocode but I actually prefer it that way. Makes you consider your implementations more

I've been using C# 4.0 by Herbert Schlidt. I had a basic understanding from other programming classes and am finding it very easy to understand.

http://www.amazon.com/C-4-0-The-Complete-Reference/dp/007174116X/ref=sr_1_3?ie=UTF8&qid=1333936598&sr=8-3

Are we OK with warez here? This is not a free book as far as I'm aware: http://www.amazon.com/Core-Techniques-Algorithms-Game-Programming/dp/0131020099

> of course. except that c++ allows you to use values that are stack-allocated and unboxed whenever you wish for it. (which should really be the vast majority of the time. one notable exception are standard containers, but if you're writing your own container library, your programming license needs to be revoked anyways.)

But you just showed us the use of an auto_ptr to get past GC problems. They manage heap objects.

> this is orders of magnitude better than copying gigabytes of tiny, fragmented, heap-allocated objects for each garbage collection pass, trust me.

Generational collection.

Here's a great book. Expensive as hell, though.

Generating Functions

Book: https://www.amazon.com/Garbage-Collection-Handbook-Management-Algorithms/dp/1420082795

Article that helped me a lot: https://journal.stuffwithstuff.com/2013/12/08/babys-first-garbage-collector/

Here's free and frequently updated book: Foundations of Data Science by Blum, Hopcroft, Kannan

Also, check out:

Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis by Mitzenmacher and Upfal.

http://www.amazon.com/Nature-Code-Simulating-Natural-Processing/dp/0985930802/ref=sr_1_2?ie=UTF8&qid=1416438876&sr=8-2&keywords=processing+daniel

Read.

I would start with this survey by Wilson. It introduces a number of simple approaches and refers to the papers that first came up with them. There's also The Garbage Collection Handbook which goes into significantly more depth.

My advice for your language is to start with a simple mark and sweep collector. Make sure you can configure how often collections are run and can make dumps of your heap whenever you want to -- you'll be in debugging hell otherwise. Once you're done with that, switching to a copy-collector and then implementing incremental collection via a read-barrier or a write-barrier is a logical next step.

Finally, don't worry about microoptimisations (yet). Garbage collectors are a terrible pain to debug even when your code is clear; if your code is clever, you'll never figure out what's going wrong.