Code hoisting doesn't reduce time.

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+12 votes

Consider these two functions and two statements S1 and S2 about them.

int work1(int *a, int i, int j) { int x = a[i+2]; a[j] = x+1; return a[i+2] - 3; } |
int work2(int *a, int i, int j) { int t1 = i+2; int t2 = a[t1]; a[j] = t2+1; return t2 - 3; } |

S1: The transformation form *work1* to *work2* is valid, i.e., for any program state and input arguments, *work2* will compute the same output and have the same effect on program state as *work1*

S2: All the transformations applied to *work1* to get *work2* will always improve the performance (i.e reduce CPU time) of *work2* compared to *work1*

- S1 is false and S2 is false
- S1 is false and S2 is true
- S1 is true and S2 is false
- S1 is true and S2 is true

+10 votes

Best answer

Consider an array a = 1 2 3 4 5 and condition i + 2 =j. Lets take i =0 and j =2 for this example.

Work 1,

x = a[0+2] = 3

a[2] = 3 + 1 = 4; which means a = 1 2 4 4 5

return a[0+2] - 3 = 4 -3 = 1

Work 2

t1 = 0 + 2 = 2

t2 = a[2] = 3

a[2] = 3 + 1 = 4, which means a = 1 2 4 4 5 again

return t2 - 3 = 3 -3 =0

Hence S1 is false when i + 2 =j. S2 will also be false, since we cant explicitly say the performance of work2 will always be better than work1.

Hence **answer is A**

+8 votes

+4

No.. it's answer is (A)..

explaination:

if (i + 2) == j

then, a[j], in work1 is modifying.. that means (a[i + 2]) is modified.. so it's returning minus three with the modified value..

but in work2, it is saving a[i + 2] in some variable, then modifying a[j], and doing minus 3 with unmodified value.. So for this program state output won't be same.. so S1 is false..

therefore (A) is correct.. both are false..

explaination:

if (i + 2) == j

then, a[j], in work1 is modifying.. that means (a[i + 2]) is modified.. so it's returning minus three with the modified value..

but in work2, it is saving a[i + 2] in some variable, then modifying a[j], and doing minus 3 with unmodified value.. So for this program state output won't be same.. so S1 is false..

therefore (A) is correct.. both are false..

+6

S2 is false because, it is given high level language.. and this is not assembly language.. and compiler is sitting between them... So it is undecidable what corresponding assembly language the compiler will generate.. We don't know what optimization option will be used for compiling.. compiler may be smart enough, he may use dirty write concept to optimize the code.. So if we say it will ALWAYS improve the performance, we can not say it just by looking the high level language.. , isn't it?.. So so S2 is false..

+3

Yes, in an actual system compiler can do anything. But in the question it says about transformations and hence we can assume a dumb compiler which straight away maps the given code to assembly code.

+1

when j=i+2 then

work1 will be

int x=a[i+2];

a[i+2]=x+1; return a[i+2]-3;

And work2 will be

int t1=i+2;

int t2=a[t1];

a[i+2]=t2+1

return t2-3 and t2 is a[i+2] so where is the difference here ?

work1 will be

int x=a[i+2];

a[i+2]=x+1; return a[i+2]-3;

And work2 will be

int t1=i+2;

int t2=a[t1];

a[i+2]=t2+1

return t2-3 and t2 is a[i+2] so where is the difference here ?

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.4k
- Digital Logic 2.1k
- Programming & DS 3.9k
- Algorithms 3.4k
- Theory of Computation 4.2k
- Compiler Design 1.6k
- Databases 3.1k
- CO & Architecture 2.7k
- Computer Networks 3.1k
- Non GATE 1.1k
- Others 1.4k
- Admissions 501
- Exam Queries 447
- Tier 1 Placement Questions 19
- Job Queries 62
- Projects 12

37,939 questions

45,453 answers

131,191 comments

48,207 users