Why FFTW3's DST Type-1 (discrete sine transform) function is slow?

I used fftw3 s FFTW_RODFT00 function, but it's very slow (as they mentioned in documents. fftw3 2.5.2 Real even/odd DFTs).

// N->Array length, input->Input Array, output->Output Array
fftw_plan plan = fftw3_r2r_1d(N, input, output, FFTW_RODFT, FFTW_ESTIMATE);

fftw_execute(plan);

//using output...

fftw_destroy_plan(plan);
fftw_cleanup();

I tried to convert dst function manually but it O(n^2) algorithms so it's slow either.

How can i calculate fast discrete sine transfrom with using FFT algorithm, not using DST Type-1 Funciton?

I found a way to calculate Discrete Sine Transform with FFTW3's FFT library function. But i should say it still slower than MATLAB dst() function (and i still don't know why). Let me simply explain what i did:

//x->Your first array with some values
//y->FFT input array
//z->FFT output array
//n->First array(x) size

#define REAL 0
#define IMAG 1

function_Name(){
const int n = 1000;
double x[n][2];

//Fill x with some value
for(i){
x[i][REAL]=i+1;
x[i][IMAG]=0;
}

fftw_complex y[(n+1)*2];
fftw_complex z[(n+1)*2];

y[0][REAL]=0;
y[0][IMAG]=0;

for(){
//Add x to y from 2. element(y[1])
}

y[n+1][REAL]=0;
y[n+1][IMAG]=0;

for(){
//Invert x and multiply by "-" and add to y
}

fftw_plan plan = fftw_plan_dft_1d((n+1)*2, y, z, FFTW_FORWARD, FFTW_ESTIMATE);

fftw_execute(plan);

**//You can use z but first you have to Invert (fliplr in MATLAB) it and take only first n elements and only IMAG parts.**

fftw_destroy_plan(plan);
fftw_cleanup();

}

I know this algorithm isn't perfect but I'm working on it to speed up and to make a clean. For speed difference between MATLAB fft() function and FFTW's FFT function is still a problem. I will open a new question about it.