inssrv adds the dependency graph you're looking for.

Standard on wheezy. Allows for parallel launch of services.

I'll spend more time in hardware init (especially on servers) and fsck (even just journal replays) than service startups for most part. Even my servers (minimal services starting) take a while to come live, mostly due to the actual workload stack coming up. Then caches get to warm up and all that jazz.

Boot time is still a very small part of this.