As an aside, my final year project for my CS degree included benchmarking different sets of SK combinators for efficiency as well as looking at different reduction algorithms.
What I found out pretty quickly is that, especially as I was running my code on a mid 80s mini computer, I had to spend as much time on allocation and garbage collection strategies as anything else. Indeed, my only really "difficult" bug was caused by my premature re-use of application nodes - I thought I was being clever re-using them immediately but it caused problems months later when I started writing recursive expressions using the non-native Y-combinator. I had no idea what was causing the problem and was really quite worried, I was stumped for days and then I had a flash of insight from nowhere while sitting on a bus that fixed the problem.
I remembered that I thought I was being awfully clever re-using application nodes aggressively - turns out this worked fine for non-recursive code or code that used the native Y-combinator in my reduction engine but failed when I used a Y defined directly in the lambda calculus. I removed this "optimization" and the problems went away.
What I always remember is that the idea as to what was causing the problem came as a complete bolt from the blue when I was thinking about something else - perhaps the first time that something like that happened to me, but certainly not the last!
What I found out pretty quickly is that, especially as I was running my code on a mid 80s mini computer, I had to spend as much time on allocation and garbage collection strategies as anything else. Indeed, my only really "difficult" bug was caused by my premature re-use of application nodes - I thought I was being clever re-using them immediately but it caused problems months later when I started writing recursive expressions using the non-native Y-combinator. I had no idea what was causing the problem and was really quite worried, I was stumped for days and then I had a flash of insight from nowhere while sitting on a bus that fixed the problem.