The algorithm of vec_dist is the following:
temp[0] = vektor1[0] - vektor2[0];
temp[1] = vektor1[1] - vektor2[1];
temp[2] = vektor1[2] - vektor2[2];
distance = sqrt(temp[0]*temp[0] + temp[1]*temp[1] + temp[2]*temp[2]);
That means it is really fast. There must be something different that slows your code/ game down, the fact that you create 500 entities at once should be the problem.
Immediately after creation set their passable flag, this will be much faster:
you = ent_create(tree...)
set(you,PASSABLE);