  We measure galaxy sizes on a sample of $\sim1200$ galaxies with confirmed
spectroscopic redshifts $2 \leq z_{spec} \leq 4.5$ in the VIMOS Ultra Deep
Survey (VUDS), representative of star-forming galaxies with $i_\mathrm{AB} \leq
25$. We first derive galaxy sizes applying a classical parametric profile
fitting method using GALFIT. We then measure the total pixel area covered by a
galaxy above a given surface brightness threshold, which overcomes the
difficulty of measuring sizes of galaxies with irregular shapes. We then
compare the results obtained for the equivalent circularized radius enclosing
100\% of the measured galaxy light $r_T^{100}$ to those obtained with the
effective radius $r_{e,\mathrm{circ}}$ measured with GALFIT. We find that the
sizes of galaxies computed with our non-parametric approach span a large range
but remain roughly constant on average with a median value $r_T^{100}\sim2.2$
kpc for galaxies with $2<z<4.5$. This is in stark contrast with the strong
downward evolution of $r_e$ with increasing redshift, down to sizes of $<1$ kpc
at $z\sim4.5$. We analyze the difference and find that parametric fitting of
complex, asymmetric, multi-component galaxies is severely underestimating their
sizes. By comparing $r_T^{100}$ with physical parameters obtained through SED
fitting we find that the star-forming galaxies that are the largest at any
redshift are, on average, more massive and more star-forming. We discover that
galaxies present more concentrated light profiles as we move towards higher
redshifts. We interpret these results as the signature of several, possibly
different, evolutionary paths of galaxies in their early stages of assembly,
including major and minor merging or star-formation in multiple bright regions.
(abridged)
