Reddit reviews Hacker's Delight (2nd Edition)
We found 15 Reddit comments about Hacker's Delight (2nd Edition). Here are the top ones, ranked by their Reddit score.
We found 15 Reddit comments about Hacker's Delight (2nd Edition). Here are the top ones, ranked by their Reddit score.
Here's my list of the classics:
General Computing
Computer Science
Software Development
Case Studies
Employment
Language-Specific
C
Python
C#
C++
Java
Linux Shell Scripts
Web Development
Ruby and Rails
Assembly
First don't think of this as "DBA" stuff - you're a developer, you need to know database technology, period. Read this rant by Dennis Forbes in response to Digg's CTO's complaints about databases it's very reminiscent of TFA.
Read Data and Reality by the late William Kent (here's a free copy) and get a fundamental understanding of "information" vs. "data". Then read Information Modeling and Relational Databases to pickup a couple practical approaches to modeling (ER & OR). Now read The Datawarehouse Toolkit to learn dimensional modeling and when to use it. Practice designing effective models, build some production databases from scratch, inherit some, revisit your old designs, learn from your mistakes, write lots and lots and lots of SQL (if you want to get tricky with SQL I suggest to pickup Celko's SQL for smarties - it's like the Hacker's Delight for SQL).
Many strange models you may encounter in the wild are actually optimizations. Some are premature, some outright stupid, and some brilliant, if you want to be able to tell one from the other then you're going to dive deep into internals. Do this generically with Modern Information Retrieval and Managing Gigabytes then for specific RDBMSs Pro SQL Server Internals, PostgreSQL Internals, Oracle CORE, etc.
Reflect on how awesome practically every modern RDBMS is as a great technological achievement for mankind and how wonderful it is to be standing on the shoulders of giants. Roll your eyes a little bit whenever you overhear another twenty-something millenial fresh CS graduate who skipped every RDBMS elective bleat about NoSQL, Mongo, whatever. Try not to fly into murderous rage when another loud-mouthed know-nothing writes at length about how bad RDBMS technology is when they couldn't be bothered to learn the most basic requisite skills and knowledge to use one competently.
Anyone who thinks this is cool should read Warren's book, "hackers delight" (https://www.amazon.com/Hackers-Delight-2nd-Henry-Warren/dp/0321842685)
I was at one of his talks a long time ago, someone professed astonishment at some of the tricks he was playing with the CPU to which he responded, "Bits go in, bits come out!"
I don't know of many C++-specific materials for performance engineering. But a surprising ingredient is math. Take a look at Hacker's Delight. It's a bunch of bit twiddling hacks derived from immutable mathematical truths.
A lot of good optimizations stem from a good understanding of the computing fabric combined with an ability to formalize abstractions that mesh well with it.
Knuth also recommends a book called Hacker's Delight, by Henry S. Warren, Jr., for an in-depth discussion of bitwise operations.
Your questions are actually very relevant for optimizing compilers (and for people who like to do bit twiddling). Many folks already mentioned division by a power of 2 - that's just shifting the bits to the right by the right number of places. Very fast. But there are also algorithms for dividing by other constants - for example, there are specific tricks for efficiently dividing by 3, 5, or 7. Compilers will look for opportunities to convert general-purpose division into one of these forms. And some times that can happen as a result of what's called "constant propagation". So you write in one place in the code a division like: "x/y", where locally you don't know what values x and y have. The compiler, however, might be able to prove that y is always 3, so it optimizes the general division to use the faster division-by-3 algorithm.
For an interesting read on this many other bit twiddling tricks, check out Hacker's Delight. It's a fun read for anyone interested in this kind of thing.
An entire book of tricks like these, for the enthusiasts: https://www.amazon.com/Hackers-Delight-2nd-Henry-Warren/dp/0321842685/
What does he like in CS? Any hint would be helpful. Has he chosen a track (most schools let you choose an area of CS to specialize in, I was sysyems but we had theory, architecture, ai, and one or two others)?
Maybe a math clcok? There are a couple good ones but I think you can design your own and we could help you get better "numbers".
I got the first edition of this as a gift and was thrilled but its very low level (bit manipulation and assembly optimizations) so won't be for everyone (if you have heard him say something positive about C programming its probably a good choice if he loves ruby on rails maybe not).
It is a tad sneaky; basically, it's an old-ish compiler trick based on the fact that x/y = x(1/y). It's possible the JVM would implement it itself, but basically that magic number is
x*(0x200000000L/3+1)
, which gets you a division by 3 shifted left by 33 bits. Hacker's Delight (terrible title, good book) goes over computing the magic numbers in hideous detail (+tables), and you can probably find it online---IIRC Agner Fog's optimization manual goes over it too. The way I computed this one was by cheating; run thisunsigned f(unsigned x) {return x / 3;}
through
gcc -O4 -S
; relevant portions of the output:// EAX holds x (input)
mov $0xAAAAAAAB, %edx
mul %edx // EDX:EAX = EAX * 0xAAAAAAAB
shr %edx
mov %edx, %eax // return EDX:EAX >> (1+32)
Mind you, this particular magic number an shift will only work for unsigned division, which is basically what you're doing.
For those interested in this, Henry Warren has a very good book covering more bitwise tricks than you can shake a stick at. It's called Hacker's Delight.
This can't go by without mentioning Henry S. Warren's Hacker's Delight (and on amazon).
Sure! These are more relevant to chess though:
https://en.wikipedia.org/wiki/Computer_chess
https://chessprogramming.wikispaces.com/
http://www.talkchess.com
http://www.chessprogramming.net
From a quick look at https://en.wikipedia.org/wiki/Computer_Go , it sounds like you need to be careful about attempting to apply chess techniques to Go (there's a section in the wiki page describing why). It sounds like your evaluation function would end up being very heavy, so if I were approaching this problem, I'd:
http://www.amazon.com/Hackers-Delight-Edition-Henry-Warren/dp/0321842685
http://www.hackersdelight.org/
This is essentially a cookbook of excellent low level bit twiddling tricks; these can massively speed up your code.
It sounds like zobrist hashes and some kind of transposition table are going to be essential, so that automated testing I mentioned is going to be really important - these are both tricky parts to implement correctly. Alpha-beta, PV search and iterative deepening sound worthwhile in go.
It does sound like it's all about the state representation for the evaluation function though. Definitely a meaty problem, good luck with it...!
I started programming at around 12 and I can assure you, if you put some effort, you can close the distance in a matter of months. My advice:
Hackers Delight
Talks about some stuff and things that you might enjoy.
(Not a hacking book)
https://www.amazon.com/Hackers-Delight-2nd-Henry-Warren/dp/0321842685
Also related, a really good but non-free book: http://www.amazon.co.uk/Hackers-Delight-Henry-S-Warren/dp/0321842685