We present a new parallel implementation of the PINpointing Orbit Crossing-Collapsed HIerarchical Objects (PINOCCHIO) algorithm, a quick tool, based on Lagrangian Perturbation Theory, for the hierarchical build-up of Dark Matter halos in cosmological volumes. To assess its ability to predict halo correlations on large scales, we compare its results with those of an N-body simulation of a 3 Gpc/h box sampled with 2048^3 particles taken from the MICE suite, matching the same seeds for the initial conditions. Thanks to the FFTW libraries and to the relatively simple design, the code shows very good scaling properties. The CPU time required by PINOCCHIO is a tiny fraction (~1/2000) of that required by the MICE simulation. Varying some of PINOCCHIO numerical parameters allows one to produce a universal mass function that lies in the range allowed by published fits, although it underestimates the MICE mass function of FoF halos in the high mass tail. We compare the matter-halo and the halo-halo power spectra with those of the MICE simulation and find that these 2-point statistics are well recovered on large scales. In particular, when catalogs are matched in number density, agreement within ten per cent is achieved for the halo power spectrum. At scales k>0.1 h/Mpc, the inaccuracy of the Zeldovich approximation in locating halo positions causes an underestimate of the power spectrum that can be modeled as a Gaussian factor with a damping scale of d=3 Mpc/h at z=0, decreasing at higher redshift. Finally, a remarkable match is obtained for the reduced halo bispectrum, showing a good description of nonlinear halo bias. Our results demonstrate the potential of PINOCCHIO as an accurate and flexible tool for generating large ensembles of mock galaxy surveys, with interesting applications for the analysis of large galaxy redshift surveys.