How long it takes to vacuum a big table

Hi all,

I wonder what is the main driving factor for vacuum's duration: the size
of the table, or the number of dead tuples it has to clean ?

We have a few big tables which are also heavily updated, and I couldn't
figure out a way to properly vacuum them. Vacuuming any of those took
very long amounts of time (I started one this morning and after ~5h30min
it's still running - and it's not even the biggest or most updated
table), which I can't really afford because it prevents other vacuum
processes on smaller tables to do their job due to the transaction open
for the long-running vacuum.

BTW, is it in any way feasible to implement to make one vacuum not
blocking other vacuums from cleaning dead tuples after the first one
started ? I know it's the transaction not the vacuum which blocks, but
then wouldn't be a way to run vacuum somehow in "out of transaction
context" mode ?

Another issue: vacuum is not responding to cancel requests, at least not
in a reasonable amount of time...

Thanks in advance,
Csaba.