LLVM ERROR: out of memory ?? How to fix this error (if its fixable)

Question

Okay I am Solving https://leetcode.com/problems/longest-increasing-subsequence/ My code is Correct and runs fine without memonization(TLE), but after memonized it gives error :

LLVM ERROR: out of memory
PLEASE submit a bug report to https://bugs.llvm.org/ and include the crash backtrace, preprocessed source, and associated run script.

My code:

class Solution {
public:
    int dp[2555][25000005];
    int fun(vector<int>& a, vector<int>& v, int i, int count) {
        int n = a.size();
        if(i == n) return count;
        if(dp[i][count] != -1) return dp[i][count];
        
        if(v.back() < a[i]) {
            v.push_back(a[i]);
            int val1 = fun(a, v, i+1, count+1);
            v.pop_back();
            int val2 = fun(a,v,i+1,count);
            return  max(val1, val2);
        }
        else
            return fun(a,v,i+1,count);
    }
    int lengthOfLIS(vector<int>& a) {
        vector<int> v;
        v.push_back(INT_MIN);
        memset(dp, -1, sizeof(dp));
        return fun(a, v, 0, 0);
    }
};

I mean wherever the code is being executed, `dp` takes up roughly 60GB, so you need at least that amount of RAM to store it. I guess you will have to think of a better solution. — Quimby, Dec 27 '20 at 17:06
Actually my math is wrong, it takes 240GB if we assume `int`s are 4 bytes. — Quimby, Dec 27 '20 at 17:07

Henry Le Berre · Accepted Answer · 2022-02-15T20:51:03.920

3

Your int dp[2555][25000005]; array is probably way too large for your stack as it is approximately 2555*25000005*4=255 GB (if an int is 4 bytes). If you have enough memory (physical and pageable) you can simply allocate all that memory on the heap by using malloc()/free() or an STL container like std::vector. Otherwise, you should probably try to make your program allocate less memory by changing your algorithm.

For further information on the stack/heap and memory and general you can look that this previous question What and where are the stack and heap?.

edited Feb 15 '22 at 20:51

answered Dec 27 '20 at 17:08

Henry Le Berre

910
9
18

Why `malloc` instead of `new[]`? – Quimby Dec 27 '20 at 17:09
1

Sorry, probably a ```std::vector```. I thought this was a ```c``` tagged question. – Henry Le Berre Dec 27 '20 at 17:10
So my algorithm should be changed now :( – Crazy happens Dec 27 '20 at 17:14
Can anyone tell me better way to memonize if its possible? – Crazy happens Dec 27 '20 at 17:18
@Crazyhappens there seem to be solutions on the website, including one which uses dynamic programing. – Henry Le Berre Dec 27 '20 at 17:29
I did a mistake there actually only ```dp[2505][2505]``` is requried there, sorry my bad. But after memonization still gives TLE – Crazy happens Dec 27 '20 at 17:34

score 1 · Answer 2 · answered Jun 06 '22 at 10:34

As for me - in the logs this @objc method UI_USER_INTERFACE_IDIOM was highlighted. So I've replaced it to Swift approach - and generation started working again.

       if UI_USER_INTERFACE_IDIOM() == UIUserInterfaceIdiom.pad {}
       if UIDevice.current.userInterfaceIdiom == .pad {}

LLVM ERROR: out of memory ?? How to fix this error (if its fixable)

2 Answers2