Code hoisting doesn't reduce time.

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+13 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

0

important difference to notice in this question is

return a[i+2] - 3; in work1

return t2 - 3; in work2

so in first one we are directly doing calculation on array value.

where as in second one we are storing value somewhere.

So there are chances that in first one value in array can get modified .

And now we have to find that combination for which it gets modified

+12 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

+5

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..

+8

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.8k
- Engineering Mathematics 7.3k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.1k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.6k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

49,845 questions

54,783 answers

189,419 comments

80,411 users