The use of a third party black box with side effects in your architecture is going to have obvious and difficult impacts on the design of your system. In order to minimize this impact you will need to isolate that code dependency from other parts of the system. There are many ways to accomplish this isolation, dependency injection is the most obvious one and easy dependency injection is one benefit of some dynamic languages. That isolation is not a result of TDD, it is a good design principle that TDD helps enforce.
As for cache cohesion, algorithmic complexity, etc. I wouldn't encode those in a test any more than I would encode a requirement to use while loops vs. recursion. I've never encountered a specification that cares about those things, rather typically you care about some performance metric, median latency, worst case latency, sustained throughput, memory usage, cpu utilization, etc. If those things are important enough to be specified, they are important enough to be automatically tested. Writing performance correctness tests first has all the same advantages as writing algorithmic correctness tests first, and I heartily recommend doing so. If I ever encountered a specification that actively cared about memory layout, I would first be suspicious of the requirement but if it turned out to be real I would spend a lot of time figuring out how to test it.
As for cache cohesion, algorithmic complexity, etc. I wouldn't encode those in a test any more than I would encode a requirement to use while loops vs. recursion. I've never encountered a specification that cares about those things, rather typically you care about some performance metric, median latency, worst case latency, sustained throughput, memory usage, cpu utilization, etc. If those things are important enough to be specified, they are important enough to be automatically tested. Writing performance correctness tests first has all the same advantages as writing algorithmic correctness tests first, and I heartily recommend doing so. If I ever encountered a specification that actively cared about memory layout, I would first be suspicious of the requirement but if it turned out to be real I would spend a lot of time figuring out how to test it.